blockchain.rs

// Copyright 2015, 2016 Ethcore (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 bloomchain as bc;
use util::*;
use rlp::*;
use header::*;
use super::extras::*;
use transaction::*;
use views::*;
use log_entry::{LogEntry, LocalizedLogEntry};
use receipt::Receipt;
use blooms::{Bloom, BloomGroup};
use blockchain::block_info::{BlockInfo, BlockLocation, BranchBecomingCanonChainData};
use blockchain::best_block::{BestBlock, BestAncientBlock};
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;

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

	/// 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| decode(&header))
	}

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

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

	/// 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(|bytes| BodyView::new(&bytes).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(|bytes| BodyView::new(&bytes).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(|bytes| self.block_number(&address.block_hash)
			.and_then(|n| BodyView::new(&bytes).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(|bytes| self.block_number(hash)
			.map(|n| BodyView::new(&bytes).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: &H2048, from_block: BlockNumber, to_block: BlockNumber) -> Vec<BlockNumber>;

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

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

impl bc::group::BloomGroupDatabase for BlockChain {
	fn blooms_at(&self, position: &bc::group::GroupPosition) -> Option<bc::group::BloomGroup> {
		let position = LogGroupPosition::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<LogGroupPosition, BloomGroup>>,
	block_receipts: RwLock<HashMap<H256, BlockReceipts>>,

	db: Arc<Database>,

	cache_man: Mutex<CacheManager<CacheID>>,

	pending_best_block: RwLock<Option<BestBlock>>,
	pending_block_hashes: RwLock<HashMap<BlockNumber, H256>>,
	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.clone())
	}

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

	/// Get block header data
	fn block_header_data(&self, hash: &H256) -> Option<Bytes> {
		// 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.hash == hash {
				return Some(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).to_vec();
				let mut write = self.block_headers.write();
				write.insert(hash.clone(), bytes.clone());
				Some(bytes)
			},
			None => None
		};

		self.cache_man.lock().note_used(CacheID::BlockHeader(hash.clone()));
		result
	}

	/// Get block body data
	fn block_body(&self, hash: &H256) -> Option<Bytes> {
		// 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.hash == hash {
				return Some(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).to_vec();
				let mut write = self.block_bodies.write();
				write.insert(hash.clone(), bytes.clone());
				Some(bytes)
			},
			None => None
		};

		self.cache_man.lock().note_used(CacheID::BlockBody(hash.clone()));

		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.clone()));
		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.clone()));
		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.clone()));
		result
	}

	/// Returns numbers of blocks containing given bloom.
	fn blocks_with_bloom(&self, bloom: &H2048, 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::from(bloom.clone()).into())
			.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, Self: Sized {
		// sort in reverse order
		blocks.sort_by(|a, b| b.cmp(a));

		let mut log_index = 0;
		let mut logs = blocks.into_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, BodyView::new(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);
				}
				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;
						log_index -= logs.len();

						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,
								log_index: current_log_index - i - 1,
							})
					})
			})
			.filter(|log_entry| matches(&log_entry.entry))
			.take(limit.unwrap_or(::std::usize::MAX))
			.collect::<Vec<LocalizedLogEntry>>();
		logs.reverse();
		logs
	}
}

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() {
			Option::None
		} else {
			let mut n = self.chain.block_details(&self.current).unwrap().parent;
			mem::swap(&mut self.current, &mut n);
			Some(n)
		}
	}
}

impl BlockChain {
	/// Create new instance of blockchain from given Genesis
	pub fn new(config: Config, genesis: &[u8], db: Arc<Database>) -> 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_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.sha3();

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

				let mut batch = DBTransaction::new(&db);
				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();

			let raw_first = bc.db.get(db::COL_EXTRA, b"first").unwrap().map(|v| v.to_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,
				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))
	}

	/// Rewind to a previous block
	#[cfg(test)]
	fn rewind(&self) -> Option<H256> {
		use db::Key;
		let mut batch =self.db.transaction();
		// track back to the best block we have in the blocks database
		if let Some(best_block_hash) = self.db.get(db::COL_EXTRA, b"best").unwrap() {
			let best_block_hash = H256::from_slice(&best_block_hash);
			if best_block_hash == self.genesis_hash() {
				return None;
			}
			if let Some(extras) = self.db.read(db::COL_EXTRA, &best_block_hash) as Option<BlockDetails> {
				type DetailsKey = Key<BlockDetails, Target=H264>;
				batch.delete(db::COL_EXTRA, &(DetailsKey::key(&best_block_hash)));
				let hash = extras.parent;
				let range = extras.number as bc::Number .. extras.number as bc::Number;
				let chain = bc::group::BloomGroupChain::new(self.blooms_config, self);
				let changes = chain.replace(&range, vec![]);
				for (k, v) in changes.into_iter() {
					batch.write(db::COL_EXTRA, &LogGroupPosition::from(k), &BloomGroup::from(v));
				}
				batch.put(db::COL_EXTRA, b"best", &hash);

				let best_block_total_difficulty = self.block_details(&hash).unwrap().total_difficulty;
				let best_block_rlp = self.block(&hash).unwrap();

				let mut best_block = self.best_block.write();
				*best_block = BestBlock {
					number: extras.number - 1,
					total_difficulty: best_block_total_difficulty,
					hash: hash,
					block: best_block_rlp,
				};
				// update parent extras
				if let Some(mut details) = self.db.read(db::COL_EXTRA, &hash) as Option<BlockDetails> {
					details.children.clear();
					batch.write(db::COL_EXTRA, &hash, &details);
				}
				self.db.write(batch).expect("Writing to db failed");
				self.block_details.write().clear();
				self.block_hashes.write().clear();
				self.block_headers.write().clear();
				self.block_bodies.write().clear();
				self.block_receipts.write().clear();
				return Some(hash);
			}
		}

		None
	}

	/// 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 }
	///   ```
	pub fn tree_route(&self, from: H256, to: H256) -> TreeRoute {
		let mut from_branch = vec![];
		let mut to_branch = vec![];

		let mut from_details = self.block_details(&from).unwrap_or_else(|| panic!("0. Expected to find details for block {:?}", from));
		let mut to_details = self.block_details(&to).unwrap_or_else(|| panic!("1. Expected to find details for block {:?}", 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).unwrap_or_else(|| panic!("2. Expected to find details for block {:?}", 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).unwrap_or_else(|| panic!("3. Expected to find details for block {:?}", 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).unwrap_or_else(|| panic!("4. Expected to find details for block {:?}", from_details.parent));

			to_branch.push(current_to);
			current_to = to_details.parent.clone();
			to_details = self.block_details(&to_details.parent).unwrap_or_else(|| panic!("5. Expected to find details for block {:?}", from_details.parent));
		}

		let index = from_branch.len();

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

		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.sha3();

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

	/// 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, block_hash: H256, child_hash: H256) {
		let mut parent_details = self.block_details(&block_hash)
			.unwrap_or_else(|| panic!("Invalid block hash: {:?}", block_hash));

		let mut batch = self.db.transaction();
		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));

		self.db.write(batch).unwrap();
	}

	#[cfg_attr(feature="dev", allow(similar_names))]
	/// 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.sha3();

		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(),
			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.sha3();
		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 total_difficulty = parent_details.total_difficulty + header.difficulty();
		let is_new_best = total_difficulty > self.best_block_total_difficulty();

		BlockInfo {
			hash: hash,
			number: number,
			total_difficulty: total_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);

				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.
	fn prepare_update(&self, batch: &mut DBTransaction, update: ExtrasUpdate, is_best: bool) {
		{
			let block_hashes: Vec<_> = update.block_details.keys().cloned().collect();

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

			let mut cache_man = self.cache_man.lock();
			for hash in block_hashes {
				cache_man.note_used(CacheID::BlockDetails(hash));
			}
		}

		{
			let mut write_receipts = self.block_receipts.write();
			batch.extend_with_cache(db::COL_EXTRA, &mut *write_receipts, update.block_receipts, CacheUpdatePolicy::Remove);
		}

		{
			let mut write_blocks_blooms = self.blocks_blooms.write();
			batch.extend_with_cache(db::COL_EXTRA, &mut *write_blocks_blooms, update.blocks_blooms, CacheUpdatePolicy::Remove);
		}

		// These cached values must be updated last with all three locks taken to avoid
		// cache decoherence
		{
			let mut best_block = self.pending_best_block.write();
			// update best block
			match update.info.location {
				BlockLocation::Branch => (),
				_ => if is_best {
					batch.put(db::COL_EXTRA, b"best", &update.info.hash);
					*best_block = Some(BestBlock {
						hash: update.info.hash,
						number: update.info.number,
						total_difficulty: update.info.total_difficulty,
						block: update.block.to_vec(),
					});
				},
			}
			let mut write_hashes = self.pending_block_hashes.write();
			let mut write_txs = self.pending_transaction_addresses.write();

			batch.extend_with_cache(db::COL_EXTRA, &mut *write_hashes, update.block_hashes, CacheUpdatePolicy::Overwrite);
			batch.extend_with_option_cache(db::COL_EXTRA, &mut *write_txs, update.transactions_addresses, CacheUpdatePolicy::Overwrite);
		}
	}

	/// Apply pending insertion updates
	pub fn commit(&self) {
		let mut pending_best_block = self.pending_best_block.write();
		let mut pending_write_hashes = self.pending_block_hashes.write();
		let mut pending_write_txs = self.pending_transaction_addresses.write();

		let mut best_block = self.best_block.write();
		let mut write_hashes = self.block_hashes.write();
		let mut write_txs = self.transaction_addresses.write();
		// update best block
		if let Some(block) = pending_best_block.take() {
			*best_block = block;
		}

		let pending_txs = mem::replace(&mut *pending_write_txs, HashMap::new());
		let (retracted_txs, enacted_txs) = pending_txs.into_iter().partition::<HashMap<_, _>, _>(|&(_, ref value)| value.is_none());

		let pending_hashes_keys: Vec<_> = pending_write_hashes.keys().cloned().collect();
		let enacted_txs_keys: Vec<_> = enacted_txs.keys().cloned().collect();

		write_hashes.extend(mem::replace(&mut *pending_write_hashes, HashMap::new()));
		write_txs.extend(enacted_txs.into_iter().map(|(k, v)| (k, v.expect("Transactions were partitioned; qed"))));

		for hash in retracted_txs.keys() {
			write_txs.remove(hash);
		}

		let mut cache_man = self.cache_man.lock();
		for n in pending_hashes_keys {
			cache_man.note_used(CacheID::BlockHashes(n));
		}

		for hash in enacted_txs_keys {
			cache_man.note_used(CacheID::TransactionAddresses(hash));
		}
	}

	/// Iterator that lists `first` and then all of `first`'s ancestors, by hash.
	pub fn ancestry_iter(&self, first: H256) -> Option<AncestryIter> {
		if self.is_known(&first) {
			Some(AncestryIter {
				current: first,
				chain: self,
			})
		} else {
			None
		}
	}

	/// Given a block's `parent`, find every block header which represents a valid possible uncle.
	pub fn find_uncle_headers(&self, parent: &H256, uncle_generations: usize) -> Option<Vec<Header>> {
		self.find_uncle_hashes(parent, uncle_generations).map(|v| v.into_iter().filter_map(|h| self.block_header(&h)).collect())
	}

	/// Given a block's `parent`, find every block hash which represents a valid possible uncle.
	pub fn find_uncle_hashes(&self, parent: &H256, uncle_generations: usize) -> Option<Vec<H256>> {
		if !self.is_known(parent) { return None; }