blockchain.rs

// Copyright 2015-2018 Parity Technologies (UK) Ltd.
// This file is part of Parity.

// Parity is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// Parity is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with Parity.  If not, see <http://www.gnu.org/licenses/>.

//! Blockchain database.

use std::collections::{HashMap, HashSet};
use std::sync::Arc;
use std::mem;
use itertools::Itertools;
use blooms_db;
use heapsize::HeapSizeOf;
use ethereum_types::{H256, Bloom, BloomRef, U256};
use parking_lot::{Mutex, RwLock};
use bytes::Bytes;
use rlp::RlpStream;
use rlp_compress::{compress, decompress, blocks_swapper};
use header::*;
use transaction::*;
use views::{BlockView, HeaderView};
use log_entry::{LogEntry, LocalizedLogEntry};
use receipt::Receipt;
use blockchain::best_block::{BestBlock, BestAncientBlock};
use blockchain::block_info::{BlockInfo, BlockLocation, BranchBecomingCanonChainData};
use blockchain::extras::{BlockReceipts, BlockDetails, TransactionAddress, EPOCH_KEY_PREFIX, EpochTransitions};
use types::blockchain_info::BlockChainInfo;
use types::tree_route::TreeRoute;
use blockchain::update::{ExtrasUpdate, ExtrasInsert};
use blockchain::{CacheSize, ImportRoute, Config};
use db::{self, Writable, Readable, CacheUpdatePolicy};
use cache_manager::CacheManager;
use encoded;
use engines::ForkChoice;
use engines::epoch::{Transition as EpochTransition, PendingTransition as PendingEpochTransition};
use rayon::prelude::*;
use ansi_term::Colour;
use kvdb::{DBTransaction, KeyValueDB};
use error::Error;
use std::path::Path;

/// Database backing `BlockChain`.
pub trait BlockChainDB: Send + Sync {
	/// Generic key value store.
	fn key_value(&self) -> &Arc<KeyValueDB>;

	/// Header blooms database.
	fn blooms(&self) -> &blooms_db::Database;

	/// Trace blooms database.
	fn trace_blooms(&self) -> &blooms_db::Database;
}

/// Generic database handler. This trait contains one function `open`. When called, it opens database with a
/// predefined config.
pub trait BlockChainDBHandler: Send + Sync {
	/// Open the predefined key-value database.
	fn open(&self, path: &Path) -> Result<Arc<BlockChainDB>, Error>;
}

/// Interface for querying blocks by hash and by number.
pub trait BlockProvider {
	/// Returns true if the given block is known
	/// (though not necessarily a part of the canon chain).
	fn is_known(&self, hash: &H256) -> bool;

	/// Returns true if the given block is known and in the canon chain.
	fn is_canon(&self, hash: &H256) -> bool {
		let is_canon = || Some(hash == &self.block_hash(self.block_number(hash)?)?);
		is_canon().unwrap_or(false)
	}

	/// Get the first block of the best part of the chain.
	/// Return `None` if there is no gap and the first block is the genesis.
	/// Any queries of blocks which precede this one are not guaranteed to
	/// succeed.
	fn first_block(&self) -> Option<H256>;

	/// Get the number of the first block.
	fn first_block_number(&self) -> Option<BlockNumber> {
		self.first_block().map(|b| self.block_number(&b).expect("First block is always set to an existing block or `None`. Existing block always has a number; qed"))
	}

	/// Get the best block of an first block sequence if there is a gap.
	fn best_ancient_block(&self) -> Option<H256>;

	/// Get the number of the first block.
	fn best_ancient_number(&self) -> Option<BlockNumber> {
		self.best_ancient_block().map(|h| self.block_number(&h).expect("Ancient block is always set to an existing block or `None`. Existing block always has a number; qed"))
	}
	/// Get raw block data
	fn block(&self, hash: &H256) -> Option<encoded::Block>;

	/// Get the familial details concerning a block.
	fn block_details(&self, hash: &H256) -> Option<BlockDetails>;

	/// Get the hash of given block's number.
	fn block_hash(&self, index: BlockNumber) -> Option<H256>;

	/// Get the address of transaction with given hash.
	fn transaction_address(&self, hash: &H256) -> Option<TransactionAddress>;

	/// Get receipts of block with given hash.
	fn block_receipts(&self, hash: &H256) -> Option<BlockReceipts>;

	/// Get the header RLP of a block.
	fn block_header_data(&self, hash: &H256) -> Option<encoded::Header>;

	/// Get the block body (uncles and transactions).
	fn block_body(&self, hash: &H256) -> Option<encoded::Body>;

	/// Get a list of uncles for a given block.
	/// Returns None if block does not exist.
	fn uncles(&self, hash: &H256) -> Option<Vec<Header>> {
		self.block_body(hash).map(|body| body.uncles())
	}

	/// Get a list of uncle hashes for a given block.
	/// Returns None if block does not exist.
	fn uncle_hashes(&self, hash: &H256) -> Option<Vec<H256>> {
		self.block_body(hash).map(|body| body.uncle_hashes())
	}

	/// Get the number of given block's hash.
	fn block_number(&self, hash: &H256) -> Option<BlockNumber> {
		self.block_header_data(hash).map(|header| header.number())
	}

	/// Get transaction with given transaction hash.
	fn transaction(&self, address: &TransactionAddress) -> Option<LocalizedTransaction> {
		self.block_body(&address.block_hash)
			.and_then(|body| self.block_number(&address.block_hash)
			.and_then(|n| body.view().localized_transaction_at(&address.block_hash, n, address.index)))
	}

	/// Get transaction receipt.
	fn transaction_receipt(&self, address: &TransactionAddress) -> Option<Receipt> {
		self.block_receipts(&address.block_hash).and_then(|br| br.receipts.into_iter().nth(address.index))
	}

	/// Get a list of transactions for a given block.
	/// Returns None if block does not exist.
	fn transactions(&self, hash: &H256) -> Option<Vec<LocalizedTransaction>> {
		self.block_body(hash)
			.and_then(|body| self.block_number(hash)
			.map(|n| body.view().localized_transactions(hash, n)))
	}

	/// Returns reference to genesis hash.
	fn genesis_hash(&self) -> H256 {
		self.block_hash(0).expect("Genesis hash should always exist")
	}

	/// Returns the header of the genesis block.
	fn genesis_header(&self) -> encoded::Header {
		self.block_header_data(&self.genesis_hash())
			.expect("Genesis header always stored; qed")
	}

	/// Returns numbers of blocks containing given bloom.
	fn blocks_with_bloom<'a, B, I, II>(&self, blooms: II, from_block: BlockNumber, to_block: BlockNumber) -> Vec<BlockNumber>
	where
		BloomRef<'a>: From<B>,
		II: IntoIterator<Item = B, IntoIter = I> + Copy,
		I: Iterator<Item = B>,
		Self: Sized;

	/// Returns logs matching given filter.
	fn logs<F>(&self, blocks: Vec<H256>, matches: F, limit: Option<usize>) -> Vec<LocalizedLogEntry>
		where F: Fn(&LogEntry) -> bool + Send + Sync, Self: Sized;
}

#[derive(Debug, Hash, Eq, PartialEq, Clone)]
enum CacheId {
	BlockHeader(H256),
	BlockBody(H256),
	BlockDetails(H256),
	BlockHashes(BlockNumber),
	TransactionAddresses(H256),
	BlockReceipts(H256),
}

/// Structure providing fast access to blockchain data.
///
/// **Does not do input data verification.**
pub struct BlockChain {
	// All locks must be captured in the order declared here.
	best_block: RwLock<BestBlock>,
	// Stores best block of the first uninterrupted sequence of blocks. `None` if there are no gaps.
	// Only updated with `insert_unordered_block`.
	best_ancient_block: RwLock<Option<BestAncientBlock>>,
	// Stores the last block of the last sequence of blocks. `None` if there are no gaps.
	// This is calculated on start and does not get updated.
	first_block: Option<H256>,

	// block cache
	block_headers: RwLock<HashMap<H256, encoded::Header>>,
	block_bodies: RwLock<HashMap<H256, encoded::Body>>,

	// extra caches
	block_details: RwLock<HashMap<H256, BlockDetails>>,
	block_hashes: RwLock<HashMap<BlockNumber, H256>>,
	transaction_addresses: RwLock<HashMap<H256, TransactionAddress>>,
	block_receipts: RwLock<HashMap<H256, BlockReceipts>>,

	db: Arc<BlockChainDB>,

	cache_man: Mutex<CacheManager<CacheId>>,

	pending_best_block: RwLock<Option<BestBlock>>,
	pending_block_hashes: RwLock<HashMap<BlockNumber, H256>>,
	pending_block_details: RwLock<HashMap<H256, BlockDetails>>,
	pending_transaction_addresses: RwLock<HashMap<H256, Option<TransactionAddress>>>,
}

impl BlockProvider for BlockChain {
	/// Returns true if the given block is known
	/// (though not necessarily a part of the canon chain).
	fn is_known(&self, hash: &H256) -> bool {
		self.db.key_value().exists_with_cache(db::COL_EXTRA, &self.block_details, hash)
	}

	fn first_block(&self) -> Option<H256> {
		self.first_block.clone()
	}

	fn best_ancient_block(&self) -> Option<H256> {
		self.best_ancient_block.read().as_ref().map(|b| b.hash)
	}

	fn best_ancient_number(&self) -> Option<BlockNumber> {
		self.best_ancient_block.read().as_ref().map(|b| b.number)
	}

	/// Get raw block data
	fn block(&self, hash: &H256) -> Option<encoded::Block> {
		let header = self.block_header_data(hash)?;
		let body = self.block_body(hash)?;
		Some(encoded::Block::new_from_header_and_body(&header.view(), &body.view()))
	}

	/// Get block header data
	fn block_header_data(&self, hash: &H256) -> Option<encoded::Header> {
		// Check cache first
		{
			let read = self.block_headers.read();
			if let Some(v) = read.get(hash) {
				return Some(v.clone());
			}
		}

		// Check if it's the best block
		{
			let best_block = self.best_block.read();
			if &best_block.header.hash() == hash {
				return Some(best_block.header.encoded())
			}
		}

		// Read from DB and populate cache
		let b = self.db.key_value().get(db::COL_HEADERS, hash)
			.expect("Low level database error. Some issue with disk?")?;

		let header = encoded::Header::new(decompress(&b, blocks_swapper()).into_vec());
		let mut write = self.block_headers.write();
		write.insert(*hash, header.clone());

		self.cache_man.lock().note_used(CacheId::BlockHeader(*hash));
		Some(header)
	}

	/// Get block body data
	fn block_body(&self, hash: &H256) -> Option<encoded::Body> {
		// Check cache first
		{
			let read = self.block_bodies.read();
			if let Some(v) = read.get(hash) {
				return Some(v.clone());
			}
		}

		// Check if it's the best block
		{
			let best_block = self.best_block.read();
			if &best_block.header.hash() == hash {
				return Some(encoded::Body::new(Self::block_to_body(best_block.block.rlp().as_raw())));
			}
		}

		// Read from DB and populate cache
		let b = self.db.key_value().get(db::COL_BODIES, hash)
			.expect("Low level database error. Some issue with disk?")?;

		let body = encoded::Body::new(decompress(&b, blocks_swapper()).into_vec());
		let mut write = self.block_bodies.write();
		write.insert(*hash, body.clone());

		self.cache_man.lock().note_used(CacheId::BlockBody(*hash));
		Some(body)
	}

	/// Get the familial details concerning a block.
	fn block_details(&self, hash: &H256) -> Option<BlockDetails> {
		let result = self.db.key_value().read_with_cache(db::COL_EXTRA, &self.block_details, hash)?;
		self.cache_man.lock().note_used(CacheId::BlockDetails(*hash));
		Some(result)
	}

	/// Get the hash of given block's number.
	fn block_hash(&self, index: BlockNumber) -> Option<H256> {
		let result = self.db.key_value().read_with_cache(db::COL_EXTRA, &self.block_hashes, &index)?;
		self.cache_man.lock().note_used(CacheId::BlockHashes(index));
		Some(result)
	}

	/// Get the address of transaction with given hash.
	fn transaction_address(&self, hash: &H256) -> Option<TransactionAddress> {
		let result = self.db.key_value().read_with_cache(db::COL_EXTRA, &self.transaction_addresses, hash)?;
		self.cache_man.lock().note_used(CacheId::TransactionAddresses(*hash));
		Some(result)
	}

	/// Get receipts of block with given hash.
	fn block_receipts(&self, hash: &H256) -> Option<BlockReceipts> {
		let result = self.db.key_value().read_with_cache(db::COL_EXTRA, &self.block_receipts, hash)?;
		self.cache_man.lock().note_used(CacheId::BlockReceipts(*hash));
		Some(result)
	}

	/// Returns numbers of blocks containing given bloom.
	fn blocks_with_bloom<'a, B, I, II>(&self, blooms: II, from_block: BlockNumber, to_block: BlockNumber) -> Vec<BlockNumber>
	where
		BloomRef<'a>: From<B>,
		II: IntoIterator<Item = B, IntoIter = I> + Copy,
		I: Iterator<Item = B> {
		self.db.blooms()
			.filter(from_block, to_block, blooms)
			.expect("Low level database error. Some issue with disk?")
	}

	/// Returns logs matching given filter. The order of logs returned will be the same as the order of the blocks
	/// provided. And it's the callers responsibility to sort blocks provided in advance.
	fn logs<F>(&self, mut blocks: Vec<H256>, matches: F, limit: Option<usize>) -> Vec<LocalizedLogEntry>
		where F: Fn(&LogEntry) -> bool + Send + Sync, Self: Sized {
		// sort in reverse order
		blocks.reverse();

		let mut logs = blocks
			.chunks(128)
			.flat_map(move |blocks_chunk| {
				blocks_chunk.into_par_iter()
					.filter_map(|hash| self.block_number(&hash).map(|r| (r, hash)))
					.filter_map(|(number, hash)| self.block_receipts(&hash).map(|r| (number, hash, r.receipts)))
					.filter_map(|(number, hash, receipts)| self.block_body(&hash).map(|ref b| (number, hash, receipts, b.transaction_hashes())))
					.flat_map(|(number, hash, mut receipts, mut hashes)| {
						if receipts.len() != hashes.len() {
							warn!("Block {} ({}) has different number of receipts ({}) to transactions ({}). Database corrupt?", number, hash, receipts.len(), hashes.len());
							assert!(false);
						}
						let mut log_index = receipts.iter().fold(0, |sum, receipt| sum + receipt.logs.len());

						let receipts_len = receipts.len();
						hashes.reverse();
						receipts.reverse();
						receipts.into_iter()
							.map(|receipt| receipt.logs)
							.zip(hashes)
							.enumerate()
							.flat_map(move |(index, (mut logs, tx_hash))| {
								let current_log_index = log_index;
								let no_of_logs = logs.len();
								log_index -= no_of_logs;

								logs.reverse();
								logs.into_iter()
									.enumerate()
									.map(move |(i, log)| LocalizedLogEntry {
										entry: log,
										block_hash: *hash,
										block_number: number,
										transaction_hash: tx_hash,
										// iterating in reverse order
										transaction_index: receipts_len - index - 1,
										transaction_log_index: no_of_logs - i - 1,
										log_index: current_log_index - i - 1,
									})
							})
							.filter(|log_entry| matches(&log_entry.entry))
							.take(limit.unwrap_or(::std::usize::MAX))
							.collect::<Vec<_>>()
					})
					.collect::<Vec<_>>()
			})
			.take(limit.unwrap_or(::std::usize::MAX))
			.collect::<Vec<LocalizedLogEntry>>();
		logs.reverse();
		logs
	}
}

/// An iterator which walks the blockchain towards the genesis.
#[derive(Clone)]
pub struct AncestryIter<'a> {
	current: H256,
	chain: &'a BlockChain,
}

impl<'a> Iterator for AncestryIter<'a> {
	type Item = H256;
	fn next(&mut self) -> Option<H256> {
		if self.current.is_zero() {
			None
		} else {
			self.chain.block_details(&self.current)
				.map(|details| mem::replace(&mut self.current, details.parent))
		}
	}
}

/// An iterator which walks the blockchain towards the genesis, with metadata information.
pub struct AncestryWithMetadataIter<'a> {
	current: H256,
	chain: &'a BlockChain,
}

impl<'a> Iterator for AncestryWithMetadataIter<'a> {
	type Item = ExtendedHeader;
	fn next(&mut self) -> Option<ExtendedHeader> {
		if self.current.is_zero() {
			None
		} else {
			let details = self.chain.block_details(&self.current);
			let header = self.chain.block_header_data(&self.current)
				.map(|h| h.decode().expect("Stored block header data is valid RLP; qed"));

			match (details, header) {
				(Some(details), Some(header)) => {
					self.current = details.parent;
					Some(ExtendedHeader {
						parent_total_difficulty: details.total_difficulty - *header.difficulty(),
						is_finalized: details.is_finalized,
						metadata: details.metadata,

						header: header,
					})
				},
				_ => {
					self.current = H256::default();
					None
				},
			}
		}
	}
}

/// An iterator which walks all epoch transitions.
/// Returns epoch transitions.
pub struct EpochTransitionIter<'a> {
	chain: &'a BlockChain,
	prefix_iter: Box<Iterator<Item=(Box<[u8]>, Box<[u8]>)> + 'a>,
}

impl<'a> Iterator for EpochTransitionIter<'a> {
	type Item = (u64, EpochTransition);

	fn next(&mut self) -> Option<Self::Item> {
		loop {
			// some epochs never occurred on the main chain.
			let (key, val) = self.prefix_iter.next()?;

			// iterator may continue beyond values beginning with this
			// prefix.
			if !key.starts_with(&EPOCH_KEY_PREFIX[..]) {
				return None
			}

			let transitions: EpochTransitions = ::rlp::decode(&val[..]).expect("decode error: the db is corrupted or the data structure has changed");

			// if there are multiple candidates, at most one will be on the
			// canon chain.
			for transition in transitions.candidates.into_iter() {
				let is_in_canon_chain = self.chain.block_hash(transition.block_number)
					.map_or(false, |hash| hash == transition.block_hash);

				// if the transition is within the block gap, there will only be
				// one candidate, and it will be from a snapshot restored from.
				let is_ancient = self.chain.first_block_number()
					.map_or(false, |first| first > transition.block_number);

				if is_ancient || is_in_canon_chain {
					return Some((transitions.number, transition))
				}
			}
		}
	}
}

impl BlockChain {
	/// Create new instance of blockchain from given Genesis.
	pub fn new(config: Config, genesis: &[u8], db: Arc<BlockChainDB>) -> BlockChain {
		// 400 is the average size of the key
		let cache_man = CacheManager::new(config.pref_cache_size, config.max_cache_size, 400);

		let mut bc = BlockChain {
			first_block: None,
			best_block: RwLock::new(BestBlock {
				// BestBlock will be overwritten anyway.
				header: Default::default(),
				total_difficulty: Default::default(),
				block: encoded::Block::new(genesis.into()),
			}),
			best_ancient_block: RwLock::new(None),
			block_headers: RwLock::new(HashMap::new()),
			block_bodies: RwLock::new(HashMap::new()),
			block_details: RwLock::new(HashMap::new()),
			block_hashes: RwLock::new(HashMap::new()),
			transaction_addresses: RwLock::new(HashMap::new()),
			block_receipts: RwLock::new(HashMap::new()),
			db: db.clone(),
			cache_man: Mutex::new(cache_man),
			pending_best_block: RwLock::new(None),
			pending_block_hashes: RwLock::new(HashMap::new()),
			pending_block_details: RwLock::new(HashMap::new()),
			pending_transaction_addresses: RwLock::new(HashMap::new()),
		};

		// load best block
		let best_block_hash = match bc.db.key_value().get(db::COL_EXTRA, b"best").unwrap() {
			Some(best) => {
				H256::from_slice(&best)
			}
			None => {
				// best block does not exist
				// we need to insert genesis into the cache
				let block = view!(BlockView, genesis);
				let header = block.header_view();
				let hash = block.hash();

				let details = BlockDetails {
					number: header.number(),
					total_difficulty: header.difficulty(),
					parent: header.parent_hash(),
					children: vec![],
					is_finalized: false,
					metadata: None,
				};

				let mut batch = DBTransaction::new();
				batch.put(db::COL_HEADERS, &hash, block.header_rlp().as_raw());
				batch.put(db::COL_BODIES, &hash, &Self::block_to_body(genesis));

				batch.write(db::COL_EXTRA, &hash, &details);
				batch.write(db::COL_EXTRA, &header.number(), &hash);

				batch.put(db::COL_EXTRA, b"best", &hash);
				bc.db.key_value().write(batch).expect("Low level database error. Some issue with disk?");
				hash
			}
		};

		{
			// Fetch best block details
			let best_block_total_difficulty = bc.block_details(&best_block_hash).unwrap().total_difficulty;
			let best_block_rlp = bc.block(&best_block_hash).unwrap();

			// and write them
			let mut best_block = bc.best_block.write();
			*best_block = BestBlock {
				total_difficulty: best_block_total_difficulty,
				header: best_block_rlp.decode_header(),
				block: best_block_rlp,
			};
		}

		{
			let best_block_number = bc.best_block.read().header.number();
			// Fetch first and best ancient block details
			let raw_first = bc.db.key_value().get(db::COL_EXTRA, b"first").unwrap().map(|v| v.into_vec());
			let mut best_ancient = bc.db.key_value().get(db::COL_EXTRA, b"ancient").unwrap().map(|h| H256::from_slice(&h));
			let best_ancient_number;
			if best_ancient.is_none() && best_block_number > 1 && bc.block_hash(1).is_none() {
				best_ancient = Some(bc.genesis_hash());
				best_ancient_number = Some(0);
			} else {
				best_ancient_number = best_ancient.as_ref().and_then(|h| bc.block_number(h));
			}

			// binary search for the first block.
			match raw_first {
				None => {
					let (mut f, mut hash) = (best_block_number, best_block_hash);
					let mut l = best_ancient_number.unwrap_or(0);

					loop {
						if l >= f { break; }

						let step = (f - l) >> 1;
						let m = l + step;

						match bc.block_hash(m) {
							Some(h) => { f = m; hash = h },
							None => { l = m + 1 },
						}
					}

					if hash != bc.genesis_hash() {
						trace!("First block calculated: {:?}", hash);
						let mut batch = db.key_value().transaction();
						batch.put(db::COL_EXTRA, b"first", &hash);
						db.key_value().write(batch).expect("Low level database error.");
						bc.first_block = Some(hash);
					}
				},
				Some(raw_first) => {
					bc.first_block = Some(H256::from_slice(&raw_first));
				},
			}

			// and write them
			if let (Some(hash), Some(number)) = (best_ancient, best_ancient_number) {
				let mut best_ancient_block = bc.best_ancient_block.write();
				*best_ancient_block = Some(BestAncientBlock {
					hash: hash,
					number: number,
				});
			}
		}

		bc
	}

	/// Returns true if the given parent block has given child
	/// (though not necessarily a part of the canon chain).
	fn is_known_child(&self, parent: &H256, hash: &H256) -> bool {
		self.db.key_value().read_with_cache(db::COL_EXTRA, &self.block_details, parent).map_or(false, |d| d.children.contains(hash))
	}

	/// Returns a tree route between `from` and `to`, which is a tuple of:
	///
	/// - a vector of hashes of all blocks, ordered from `from` to `to`.
	///
	/// - common ancestor of these blocks.
	///
	/// - an index where best common ancestor would be
	///
	/// 1.) from newer to older
	///
	/// - bc: `A1 -> A2 -> A3 -> A4 -> A5`
	/// - from: A5, to: A4
	/// - route:
	///
	///   ```json
	///   { blocks: [A5], ancestor: A4, index: 1 }
	///   ```
	///
	/// 2.) from older to newer
	///
	/// - bc: `A1 -> A2 -> A3 -> A4 -> A5`
	/// - from: A3, to: A4
	/// - route:
	///
	///   ```json
	///   { blocks: [A4], ancestor: A3, index: 0 }
	///   ```
	///
	/// 3.) fork:
	///
	/// - bc:
	///
	///   ```text
	///   A1 -> A2 -> A3 -> A4
	///              -> B3 -> B4
	///   ```
	/// - from: B4, to: A4
	/// - route:
	///
	///   ```json
	///   { blocks: [B4, B3, A3, A4], ancestor: A2, index: 2 }
	///   ```
	///
	/// If the tree route verges into pruned or unknown blocks,
	/// `None` is returned.
	pub fn tree_route(&self, from: H256, to: H256) -> Option<TreeRoute> {
		let mut from_branch = vec![];
		let mut is_from_route_finalized = false;
		let mut to_branch = vec![];

		let mut from_details = self.block_details(&from)?;
		let mut to_details = self.block_details(&to)?;
		let mut current_from = from;
		let mut current_to = to;

		// reset from && to to the same level
		while from_details.number > to_details.number {
			from_branch.push(current_from);
			current_from = from_details.parent.clone();
			from_details = self.block_details(&from_details.parent)?;
			is_from_route_finalized = is_from_route_finalized || from_details.is_finalized;
		}

		while to_details.number > from_details.number {
			to_branch.push(current_to);
			current_to = to_details.parent.clone();
			to_details = self.block_details(&to_details.parent)?;
		}

		assert_eq!(from_details.number, to_details.number);

		// move to shared parent
		while current_from != current_to {
			from_branch.push(current_from);
			current_from = from_details.parent.clone();
			from_details = self.block_details(&from_details.parent)?;
			is_from_route_finalized = is_from_route_finalized || from_details.is_finalized;

			to_branch.push(current_to);
			current_to = to_details.parent.clone();
			to_details = self.block_details(&to_details.parent)?;
		}

		let index = from_branch.len();

		from_branch.extend(to_branch.into_iter().rev());

		Some(TreeRoute {
			blocks: from_branch,
			ancestor: current_from,
			index: index,
			is_from_route_finalized: is_from_route_finalized,
		})
	}

	/// Inserts a verified, known block from the canonical chain.
	///
	/// Can be performed out-of-order, but care must be taken that the final chain is in a correct state.
	/// This is used by snapshot restoration and when downloading missing blocks for the chain gap.
	/// `is_best` forces the best block to be updated to this block.
	/// `is_ancient` forces the best block of the first block sequence to be updated to this block.
	/// `parent_td` is a parent total diffuculty
	/// Supply a dummy parent total difficulty when the parent block may not be in the chain.
	/// Returns true if the block is disconnected.
	pub fn insert_unordered_block(&self, batch: &mut DBTransaction, bytes: &[u8], receipts: Vec<Receipt>, parent_td: Option<U256>, is_best: bool, is_ancient: bool) -> bool {
		let block = view!(BlockView, bytes);
		let header = block.header_view();
		let hash = header.hash();

		if self.is_known(&hash) {
			return false;
		}

		assert!(self.pending_best_block.read().is_none());

		let compressed_header = compress(block.header_rlp().as_raw(), blocks_swapper());
		let compressed_body = compress(&Self::block_to_body(bytes), blocks_swapper());

		// store block in db
		batch.put(db::COL_HEADERS, &hash, &compressed_header);
		batch.put(db::COL_BODIES, &hash, &compressed_body);

		let maybe_parent = self.block_details(&header.parent_hash());

		if let Some(parent_details) = maybe_parent {
			// parent known to be in chain.
			let info = BlockInfo {
				hash: hash,
				number: header.number(),
				total_difficulty: parent_details.total_difficulty + header.difficulty(),
				location: BlockLocation::CanonChain,
			};

			self.prepare_update(batch, ExtrasUpdate {
				block_hashes: self.prepare_block_hashes_update(bytes, &info),
				block_details: self.prepare_block_details_update(bytes, &info, false, None),
				block_receipts: self.prepare_block_receipts_update(receipts, &info),
				blocks_blooms: self.prepare_block_blooms_update(bytes, &info),
				transactions_addresses: self.prepare_transaction_addresses_update(bytes, &info),
				info: info,
				block: bytes
			}, is_best);

			if is_ancient {
				let mut best_ancient_block = self.best_ancient_block.write();
				let ancient_number = best_ancient_block.as_ref().map_or(0, |b| b.number);
				if self.block_hash(header.number() + 1).is_some() {
					batch.delete(db::COL_EXTRA, b"ancient");
					*best_ancient_block = None;
				} else if header.number() > ancient_number {
					batch.put(db::COL_EXTRA, b"ancient", &hash);
					*best_ancient_block = Some(BestAncientBlock {
						hash: hash,
						number: header.number(),
					});
				}
			}

			false
		} else {
			// parent not in the chain yet. we need the parent difficulty to proceed.
			let d = parent_td
				.expect("parent total difficulty always supplied for first block in chunk. only first block can have missing parent; qed");

			let info = BlockInfo {
				hash: hash,
				number: header.number(),
				total_difficulty: d + header.difficulty(),
				location: BlockLocation::CanonChain,
			};

			// TODO [sorpaas] support warp sync insertion of finalization and metadata.
			let block_details = BlockDetails {
				number: header.number(),
				total_difficulty: info.total_difficulty,
				parent: header.parent_hash(),
				children: Vec::new(),
				is_finalized: false,
				metadata: None,
			};

			let mut update = HashMap::new();
			update.insert(hash, block_details);

			self.prepare_update(batch, ExtrasUpdate {
				block_hashes: self.prepare_block_hashes_update(bytes, &info),
				block_details: update,
				block_receipts: self.prepare_block_receipts_update(receipts, &info),
				blocks_blooms: self.prepare_block_blooms_update(bytes, &info),
				transactions_addresses: self.prepare_transaction_addresses_update(bytes, &info),
				info: info,
				block: bytes,
			}, is_best);
			true
		}
	}

	/// Insert an epoch transition. Provide an epoch number being transitioned to
	/// and epoch transition object.
	///
	/// The block the transition occurred at should have already been inserted into the chain.
	pub fn insert_epoch_transition(&self, batch: &mut DBTransaction, epoch_num: u64, transition: EpochTransition) {
		let mut transitions = match self.db.key_value().read(db::COL_EXTRA, &epoch_num) {
			Some(existing) => existing,
			None => EpochTransitions {
				number: epoch_num,
				candidates: Vec::with_capacity(1),
			}
		};

		// ensure we don't write any duplicates.
		if transitions.candidates.iter().find(|c| c.block_hash == transition.block_hash).is_none() {
			transitions.candidates.push(transition);
			batch.write(db::COL_EXTRA, &epoch_num, &transitions);
		}
	}

	/// Iterate over all epoch transitions.
	/// This will only return transitions within the canonical chain.
	pub fn epoch_transitions(&self) -> EpochTransitionIter {
		let iter = self.db.key_value().iter_from_prefix(db::COL_EXTRA, &EPOCH_KEY_PREFIX[..]);
		EpochTransitionIter {
			chain: self,
			prefix_iter: iter,
		}
	}

	/// Get a specific epoch transition by block number and provided block hash.
	pub fn epoch_transition(&self, block_num: u64, block_hash: H256) -> Option<EpochTransition> {
		trace!(target: "blockchain", "Loading epoch transition at block {}, {}",
			block_num, block_hash);

		self.db.key_value().read(db::COL_EXTRA, &block_num).and_then(|transitions: EpochTransitions| {
			transitions.candidates.into_iter().find(|c| c.block_hash == block_hash)
		})
	}

	/// Get the transition to the epoch the given parent hash is part of
	/// or transitions to.
	/// This will give the epoch that any children of this parent belong to.
	///
	/// The block corresponding the the parent hash must be stored already.
	pub fn epoch_transition_for(&self, parent_hash: H256) -> Option<EpochTransition> {
		// slow path: loop back block by block
		for hash in self.ancestry_iter(parent_hash)? {
			let details = self.block_details(&hash)?;

			// look for transition in database.
			if let Some(transition) = self.epoch_transition(details.number, hash) {
				return Some(transition)
			}

			// canonical hash -> fast breakout:
			// get the last epoch transition up to this block.
			//
			// if `block_hash` is canonical it will only return transitions up to
			// the parent.
			if self.block_hash(details.number)? == hash {
				return self.epoch_transitions()
					.map(|(_, t)| t)
					.take_while(|t| t.block_number <= details.number)
					.last()
			}
		}

		// should never happen as the loop will encounter genesis before concluding.
		None
	}

	/// Write a pending epoch transition by block hash.
	pub fn insert_pending_transition(&self, batch: &mut DBTransaction, hash: H256, t: PendingEpochTransition) {
		batch.write(db::COL_EXTRA, &hash, &t);
	}

	/// Get a pending epoch transition by block hash.
	// TODO: implement removal safely: this can only be done upon finality of a block
	// that _uses_ the pending transition.
	pub fn get_pending_transition(&self, hash: H256) -> Option<PendingEpochTransition> {
		self.db.key_value().read(db::COL_EXTRA, &hash)
	}

	/// Add a child to a given block. Assumes that the block hash is in
	/// the chain and the child's parent is this block.
	///
	/// Used in snapshots to glue the chunks together at the end.
	pub fn add_child(&self, batch: &mut DBTransaction, block_hash: H256, child_hash: H256) {
		let mut parent_details = self.block_details(&block_hash)
			.unwrap_or_else(|| panic!("Invalid block hash: {:?}", block_hash));

		parent_details.children.push(child_hash);

		let mut update = HashMap::new();
		update.insert(block_hash, parent_details);

		let mut write_details = self.block_details.write();
		batch.extend_with_cache(db::COL_EXTRA, &mut *write_details, update, CacheUpdatePolicy::Overwrite);

		self.cache_man.lock().note_used(CacheId::BlockDetails(block_hash));
	}

	/// Inserts the block into backing cache database.
	/// Expects the block to be valid and already verified.
	/// If the block is already known, does nothing.
	pub fn insert_block(&self, batch: &mut DBTransaction, bytes: &[u8], receipts: Vec<Receipt>, extras: ExtrasInsert) -> ImportRoute {
		let block = view!(BlockView, bytes);
		let header = block.header_view();

		let parent_hash = header.parent_hash();
		let best_hash = self.best_block_hash();

		let route = self.tree_route(best_hash, parent_hash).expect("forks are only kept when it has common ancestors; tree route from best to prospective's parent always exists; qed");

		self.insert_block_with_route(batch, bytes, receipts, route, extras)
	}

	/// Inserts the block into backing cache database with already generated route information.
	/// Expects the block to be valid and already verified and route is tree route information from current best block to new block's parent.
	/// If the block is already known, does nothing.
	pub fn insert_block_with_route(&self, batch: &mut DBTransaction, bytes: &[u8], receipts: Vec<Receipt>, route: TreeRoute, extras: ExtrasInsert) -> ImportRoute {
		// create views onto rlp
		let block = view!(BlockView, bytes);
		let header = block.header_view();
		let hash = header.hash();

		if self.is_known_child(&header.parent_hash(), &hash) {
			return ImportRoute::none();
		}

		assert!(self.pending_best_block.read().is_none());

		let compressed_header = compress(block.header_rlp().as_raw(), blocks_swapper());
		let compressed_body = compress(&Self::block_to_body(bytes), blocks_swapper());

		// store block in db
		batch.put(db::COL_HEADERS, &hash, &compressed_header);
		batch.put(db::COL_BODIES, &hash, &compressed_body);

		let info = self.block_info(&header, route, &extras);

		if let BlockLocation::BranchBecomingCanonChain(ref d) = info.location {
			info!(target: "reorg", "Reorg to {} ({} {} {})",
				Colour::Yellow.bold().paint(format!("#{} {}", info.number, info.hash)),
				Colour::Red.paint(d.retracted.iter().join(" ")),
				Colour::White.paint(format!("#{} {}", self.block_details(&d.ancestor).expect("`ancestor` is in the route; qed").number, d.ancestor)),
				Colour::Green.paint(d.enacted.iter().join(" "))
			);
		}

		self.prepare_update(batch, ExtrasUpdate {
			block_hashes: self.prepare_block_hashes_update(bytes, &info),
			block_details: self.prepare_block_details_update(bytes, &info, extras.is_finalized, extras.metadata),
			block_receipts: self.prepare_block_receipts_update(receipts, &info),