blockchain.rs

// Copyright 2015-2017 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 bloomchain as bc;
use heapsize::HeapSizeOf;
use ethereum_types::{H256, Bloom, U256};
use parking_lot::{Mutex, RwLock};
use bytes::Bytes;
use rlp::*;
use header::*;
use transaction::*;
use views::*;
use log_entry::{LogEntry, LocalizedLogEntry};
use receipt::Receipt;
use blooms::{BloomGroup, GroupPosition};
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;
use blockchain::{CacheSize, ImportRoute, Config};
use db::{self, Writable, Readable, CacheUpdatePolicy};
use cache_manager::CacheManager;
use encoded;
use engines::epoch::{Transition as EpochTransition, PendingTransition as PendingEpochTransition};
use rayon::prelude::*;
use ansi_term::Colour;
use kvdb::{DBTransaction, KeyValueDB};

const LOG_BLOOMS_LEVELS: usize = 3;
const LOG_BLOOMS_ELEMENTS_PER_INDEX: usize = 16;

/// 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;

	/// 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 partial-header of a block.
	fn block_header(&self, hash: &H256) -> Option<Header> {
		self.block_header_data(hash).map(|header| header.decode())
	}

	/// 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_details(hash).map(|details| details.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) -> Header {
		self.block_header(&self.genesis_hash())
			.expect("Genesis header always stored; qed")
	}

	/// Returns numbers of blocks containing given bloom.
	fn blocks_with_bloom(&self, bloom: &Bloom, from_block: BlockNumber, to_block: BlockNumber) -> Vec<BlockNumber>;

	/// Returns logs matching given filter.
	fn logs<F>(&self, blocks: Vec<BlockNumber>, 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),
	BlocksBlooms(GroupPosition),
	BlockReceipts(H256),
}

impl bc::group::BloomGroupDatabase for BlockChain {
	fn blooms_at(&self, position: &bc::group::GroupPosition) -> Option<bc::group::BloomGroup> {
		let position = GroupPosition::from(position.clone());
		let result = self.db.read_with_cache(db::COL_EXTRA, &self.blocks_blooms, &position).map(Into::into);
		self.cache_man.lock().note_used(CacheId::BlocksBlooms(position));
		result
	}
}

/// 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.
	blooms_config: bc::Config,

	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, Bytes>>,
	block_bodies: RwLock<HashMap<H256, Bytes>>,

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

	db: Arc<KeyValueDB>,

	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.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> {
		match (self.block_header_data(hash), self.block_body(hash)) {
			(Some(header), Some(body)) => {
				let mut block = RlpStream::new_list(3);
				let body_rlp = body.rlp();
				block.append_raw(header.rlp().as_raw(), 1);
				block.append_raw(body_rlp.at(0).as_raw(), 1);
				block.append_raw(body_rlp.at(1).as_raw(), 1);
				Some(encoded::Block::new(block.out()))
			},
			_ => None,
		}
	}

	/// 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(encoded::Header::new(v.clone()));
			}
		}

		// Check if it's the best block
		{
			let best_block = self.best_block.read();
			if &best_block.hash == hash {
				return Some(encoded::Header::new(
					Rlp::new(&best_block.block).at(0).as_raw().to_vec()
				))
			}
		}

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

		let result = match opt {
			Some(b) => {
				let bytes: Bytes = UntrustedRlp::new(&b).decompress(RlpType::Blocks).into_vec();
				let mut write = self.block_headers.write();
				write.insert(*hash, bytes.clone());
				Some(encoded::Header::new(bytes))
			},
			None => None
		};

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

	/// 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(encoded::Body::new(v.clone()));
			}
		}

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

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

		let result = match opt {
			Some(b) => {
				let bytes: Bytes = UntrustedRlp::new(&b).decompress(RlpType::Blocks).into_vec();
				let mut write = self.block_bodies.write();
				write.insert(*hash, bytes.clone());
				Some(encoded::Body::new(bytes))
			},
			None => None
		};

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

		result
	}

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

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

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

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

	/// Returns numbers of blocks containing given bloom.
	fn blocks_with_bloom(&self, bloom: &Bloom, from_block: BlockNumber, to_block: BlockNumber) -> Vec<BlockNumber> {
		let range = from_block as bc::Number..to_block as bc::Number;
		let chain = bc::group::BloomGroupChain::new(self.blooms_config, self);
		chain.with_bloom(&range, bloom)
			.into_iter()
			.map(|b| b as BlockNumber)
			.collect()
	}

	fn logs<F>(&self, mut blocks: Vec<BlockNumber>, matches: F, limit: Option<usize>) -> Vec<LocalizedLogEntry>
		where F: Fn(&LogEntry) -> bool + Send + Sync, Self: Sized {
		// sort in reverse order
		blocks.sort_by(|a, b| b.cmp(a));

		let mut logs = blocks
			.chunks(128)
			.flat_map(move |blocks_chunk| {
				blocks_chunk.into_par_iter()
					.filter_map(|number| self.block_hash(*number).map(|hash| (*number, 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 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 {
			match self.prefix_iter.next() {
				Some((key, val)) => {
					// iterator may continue beyond values beginning with this
					// prefix.
					if !key.starts_with(&EPOCH_KEY_PREFIX[..]) { return None }

					let transitions: EpochTransitions = ::rlp::decode(&val[..]);

					// 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))
						}
					}

					// some epochs never occurred on the main chain.
				}
				None => return None,
			}
		}
	}
}

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

		let mut bc = BlockChain {
			blooms_config: bc::Config {
				levels: LOG_BLOOMS_LEVELS,
				elements_per_index: LOG_BLOOMS_ELEMENTS_PER_INDEX,
			},
			first_block: None,
			best_block: RwLock::new(BestBlock::default()),
			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()),
			blocks_blooms: 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.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 = BlockView::new(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![],
				};

				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.write(batch).expect("Low level database error. Some issue with disk?");
				hash
			}
		};

		{
			// Fetch best block details
			let best_block_number = bc.block_number(&best_block_hash).unwrap();
			let best_block_total_difficulty = bc.block_details(&best_block_hash).unwrap().total_difficulty;
			let best_block_rlp = bc.block(&best_block_hash).unwrap().into_inner();
			let best_block_timestamp = BlockView::new(&best_block_rlp).header().timestamp();

			let raw_first = bc.db.get(db::COL_EXTRA, b"first").unwrap().map(|v| v.into_vec());
			let mut best_ancient = bc.db.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.transaction();
						batch.put(db::COL_EXTRA, b"first", &hash);
						db.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
			let mut best_block = bc.best_block.write();
			*best_block = BestBlock {
				number: best_block_number,
				total_difficulty: best_block_total_difficulty,
				hash: best_block_hash,
				timestamp: best_block_timestamp,
				block: best_block_rlp,
			};

			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.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 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)?;
		}

		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)?;

			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
		})
	}

	/// 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.
	/// 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 = BlockView::new(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 block_rlp = UntrustedRlp::new(bytes);
		let compressed_header = block_rlp.at(0).unwrap().compress(RlpType::Blocks);
		let compressed_body = UntrustedRlp::new(&Self::block_to_body(bytes)).compress(RlpType::Blocks);

		// 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),
				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,
				timestamp: header.timestamp(),
				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,
			};

			let block_details = BlockDetails {
				number: header.number(),
				total_difficulty: info.total_difficulty,
				parent: header.parent_hash(),
				children: Vec::new(),
			};

			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,
				timestamp: header.timestamp(),
				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.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.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.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.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>) -> ImportRoute {
		// create views onto rlp
		let block = BlockView::new(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());

		// store block in db
		batch.put_compressed(db::COL_HEADERS, &hash, block.header_rlp().as_raw().to_vec());
		batch.put_compressed(db::COL_BODIES, &hash, Self::block_to_body(bytes));

		let info = self.block_info(&header);

		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),
			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.clone(),
			timestamp: header.timestamp(),
			block: bytes,
		}, true);

		ImportRoute::from(info)
	}

	/// Get inserted block info which is critical to prepare extras updates.
	fn block_info(&self, header: &HeaderView) -> BlockInfo {
		let hash = header.hash();
		let number = header.number();
		let parent_hash = header.parent_hash();
		let parent_details = self.block_details(&parent_hash).unwrap_or_else(|| panic!("Invalid parent hash: {:?}", parent_hash));
		let is_new_best = parent_details.total_difficulty + header.difficulty() > self.best_block_total_difficulty();

		BlockInfo {
			hash: hash,
			number: number,
			total_difficulty: parent_details.total_difficulty + header.difficulty(),
			location: if is_new_best {
				// on new best block we need to make sure that all ancestors
				// are moved to "canon chain"
				// find the route between old best block and the new one
				let best_hash = self.best_block_hash();
				let route = self.tree_route(best_hash, parent_hash)
					.expect("blocks being imported always within recent history; qed");

				assert_eq!(number, parent_details.number + 1);

				match route.blocks.len() {
					0 => BlockLocation::CanonChain,
					_ => {
						let retracted = route.blocks.iter().take(route.index).cloned().collect::<Vec<_>>().into_iter().collect::<Vec<_>>();
						let enacted = route.blocks.into_iter().skip(route.index).collect::<Vec<_>>();
						BlockLocation::BranchBecomingCanonChain(BranchBecomingCanonChainData {
							ancestor: route.ancestor,
							enacted: enacted,
							retracted: retracted,
						})
					}
				}
			} else {
				BlockLocation::Branch
			}
		}
	}

	/// Prepares extras update.