This is an archive of the discontinued Mercurial Phabricator instance.

Status	Author	Revision
Closed	quark	D1711 clindex: remove broken caches if things go wrong
Abandoned	quark	D1521 clindex: use childmap to calculate phases
Abandoned	quark	D1520 clindex: integrate Rust childmap
Abandoned	quark	D1519 childmap: add a map for efficient children query
Abandoned	quark	D1518 nodemap: move some methods to changelog utils

Diff 4462

rust/indexes/src/childmap.rs

This file was added.

				// Copyright 2017 Facebook, Inc.
				//
				// This software may be used and distributed according to the terms of the
				// GNU General Public License version 2 or any later version.

				use errors::{Result, ErrorKind};
				use std::mem::transmute;
				use std::slice;
				use std::u32;
				use radixbuf::key::{FixedKey, KeyId};
				use radixbuf::radix::{radix_lookup, radix_insert_with_key, RADIX_NCHILDREN};
				use radixbuf::errors as rerrors;
				use changelog_utils::{changelog_end_rev, rev_to_node, CHANGELOG_ENTRY_SIZE,
				CHANGELOG_ENTRY_P1_OFFSET, CHANGELOG_ENTRY_NODE_OFFSET};

				/// An index with rev -> a list of rev mapping intended for storing children.
				///
				/// Revision numbers are used to make the index compact. Insertion does not
				/// have to be topo order.
				///
				/// Assume revision r+1 is likely a child of revision r so that does not
				/// have to be stored in the index but will be checked using changelog.i
				/// during lookups.
				///
				/// Similar to nodemap, it has an on-disk immutable index and an im-memory
				/// side index. The "key buffer" (see radixbuf::radix for what a key buffer
				/// is) is not changelog.i but the following format:
				///
				/// key-buffer := key-buffer-len (u32) \| key-buffer + key-entry
				/// key-entry := rev (u32) + key-entry-offset (u32)
				///
				/// Child revs are stored in a linked list. key-entry-offset might be
				/// rewritten in-place so the "key buffer" is not append-only.
				///
				/// Similar to nodemap, the main radix buffer has a tiny header that is
				/// used to verify if the index is broken or not. That is:
				///
				/// raidx-buffer := radix-buffer-size (u32) + next-rev (u32)
				/// + last-node ([u8; 20])
				///
				/// When serializing to disk, the two buffers need to be merged into one:
				///
				/// childmap := radix-buffer + key-buffer
				pub struct ChildRevMap<C, I> {
				changelogi: C,
				end_rev: u32,
				main_index: I, // Immutable main index
				side_index: (Vec<u32>, Vec<u32>), // Mutable side index (key, radix)
				}

				// Offsets in the main radix and key buffers
				const RADIX_LEN_OFFSET: usize = 0;
				const RADIX_NEXT_REV_OFFSET: usize = 1;
				const RADIX_LAST_NODE_OFFSET: usize = 2;
				const RADIX_LAST_NODE_LEN: usize = 5;
				const RADIX_HEADER_LEN: usize = RADIX_LAST_NODE_OFFSET + RADIX_LAST_NODE_LEN;
				const KEY_LEN_OFFSET: usize = 0;

				// Offsets of root nodes in radix buffers
				const MAIN_RADIX_OFFSET: u32 = RADIX_HEADER_LEN as u32;
				const SIDE_RADIX_OFFSET: u32 = 0;

				impl<C, I> ChildRevMap<C, I>
				where
				C: AsRef<[u8]>,
				I: AsRef<[u32]>,
				{
				/// Initialize ChildRevMap from a non-inlined version of changelog.i and an incomplete index.
				pub fn new(changelogi: C, main_index: I) -> Result<Self> {
				// The index must contain at least 24 elements:
				// - index[0]: radix buffer size
				// - index[1]: next rev
				// - index[2..7]: last node
				// - index[7..7+16]: first radix node entry
				// - index[23]: padding in key-buffer
				if main_index.as_ref().len() < RADIX_HEADER_LEN + RADIX_NCHILDREN {
				bail!(ErrorKind::IndexCorrupted);
				}

				// Check if length matches
				let radix_buf_len = u32::from_be(main_index.as_ref()[RADIX_LEN_OFFSET]) as usize;
				if radix_buf_len >= main_index.as_ref().len() {
				bail!(ErrorKind::IndexCorrupted);
				}
				let key_buf_len = u32::from_be(main_index.as_ref()[radix_buf_len as usize]) as usize;
				if key_buf_len == 0 \|\| radix_buf_len + key_buf_len != main_index.as_ref().len() {
				bail!(ErrorKind::IndexCorrupted);
				}

				// Check if next_rev and last_node in index match changelog.i
				let next_rev = u32::from_be(main_index.as_ref()[RADIX_NEXT_REV_OFFSET]);
				let end_rev = changelog_end_rev(&changelogi);

				if next_rev > end_rev {
				bail!(ErrorKind::IndexCorrupted);
				} else if next_rev > 0 {
				let node_index: [u8; 20] = unsafe {
				let mut buf = [0u32; RADIX_LAST_NODE_LEN];
				buf.copy_from_slice(
				&main_index.as_ref()[RADIX_LAST_NODE_OFFSET..
				RADIX_LAST_NODE_OFFSET + RADIX_LAST_NODE_LEN],
				);
				transmute(buf)
				};
				let node_changelog = rev_to_node(&changelogi, (next_rev - 1).into())?;
				if &node_index[..] != node_changelog {
				bail!(ErrorKind::IndexCorrupted);
				}
				}

				// Build side_index for the revisions not in the main index
				let mut side_index = (vec![0u32; 16], vec![0u32; 1]);
				build(
				changelogi.as_ref(),
				&mut side_index.0,
				&mut side_index.1,
				SIDE_RADIX_OFFSET,
				next_rev,
				end_rev,
				)?;

				Ok(ChildRevMap {
				changelogi,
				end_rev,
				main_index,
				side_index,
				})
				}

				/// Return an empty index that can be used as "main_index" when passed to `new`.
				pub fn empty_index_buffer() -> Vec<u32> {
				let mut result = vec![0u32; RADIX_HEADER_LEN + RADIX_NCHILDREN];
				result[RADIX_LEN_OFFSET] = (result.len() as u32).to_be();
				let mut key_buf = vec![0u32];
				key_buf[KEY_LEN_OFFSET] = (key_buf.len() as u32).to_be();
				result.append(&mut key_buf);
				return result;
				}

				/// Return parent revisions.
				/// This is made compatible with hg for convenience. If the source of truth
				/// supports more than 2 parents. The signature of this function should
				/// change.
				pub fn parentrevs(&self, rev: u32) -> Option<(i32, i32)> {
				if rev >= self.end_rev {
				None
				} else {
				Some(parents(self.changelogi.as_ref(), rev))
				}
				}

				/// Get a list of child revisions for a given revision.
				pub fn lookup(&self, rev: i32) -> Result<Vec<i32>> {
				let mut childrevs = Vec::with_capacity(1);
				// Check main index
				lookup(
				&self.main_index,
				&self.main_key_buf(),
				MAIN_RADIX_OFFSET,
				rev,
				&mut childrevs,
				)?;

				// Check side index
				lookup(
				&self.side_index.0,
				&self.side_index.1,
				SIDE_RADIX_OFFSET,
				rev,
				&mut childrevs,
				)?;

				// Check changelog.i, rev + 1
				match self.parentrevs((rev + 1) as u32) {
				None => (),
				Some((p1, p2)) => {
				if (p1 == rev) \|\| (p2 >= 0 && p2 == rev) {
				childrevs.push(rev + 1)
				}
				}
				}

				childrevs.sort();
				Ok(childrevs)
				}

				/// How many revisions the side index has.
				pub fn lag(&self) -> u32 {
				let next_rev = u32::from_be(self.main_index.as_ref()[RADIX_NEXT_REV_OFFSET]);
				self.end_rev - next_rev
				}

				/// Incrementally build the main index based on the existing one.
				pub fn build_incrementally(&self) -> Result<Vec<u32>> {
				// Copy the main index since we need to modify it.
				let radix_len = self.main_radix_len();
				let mut radix_buf = self.main_index.as_ref()[0..radix_len].to_vec();
				let mut key_buf = self.main_key_buf().to_vec();
				let next_rev = u32::from_be(radix_buf[RADIX_NEXT_REV_OFFSET]);
				build(
				self.changelogi.as_ref(),
				&mut radix_buf,
				&mut key_buf,
				MAIN_RADIX_OFFSET,
				next_rev,
				self.end_rev,
				)?;

				assert!(radix_buf.len() <= u32::MAX as usize \|\| key_buf.len() <= u32::MAX as usize);

				// Rewrite headers
				radix_buf[RADIX_LEN_OFFSET] = (radix_buf.len() as u32).to_be();
				radix_buf[RADIX_NEXT_REV_OFFSET] = self.end_rev.to_be();
				if self.end_rev > 0 {
				let offset = (self.end_rev - 1) * CHANGELOG_ENTRY_SIZE as u32 +
				CHANGELOG_ENTRY_NODE_OFFSET as u32;
				let node = FixedKey::read(&self.changelogi, offset.into())?;
				let mut buf = [0u8; 20];
				buf.copy_from_slice(&node);
				let buf: [u32; RADIX_LAST_NODE_LEN] = unsafe { transmute(buf) };
				radix_buf[RADIX_LAST_NODE_OFFSET..RADIX_LAST_NODE_OFFSET + RADIX_LAST_NODE_LEN]
				.copy_from_slice(&buf);
				}
				key_buf[KEY_LEN_OFFSET] = (key_buf.len() as u32).to_be();

				radix_buf.append(&mut key_buf);
				Ok(radix_buf)
				}

				#[inline]
				fn main_radix_len(&self) -> usize {
				u32::from_be(self.main_index.as_ref()[RADIX_LEN_OFFSET]) as usize
				}

				#[inline]
				fn main_key_buf(&self) -> &[u32] { &self.main_index.as_ref()[self.main_radix_len()..] }
				}

				#[inline]
				fn parents(changelog: &[u8], rev: u32) -> (i32, i32) {
				let revs: [i32; 2] = unsafe {
				let mut buf = [0u8; 8];
				let offset = rev as usize * CHANGELOG_ENTRY_SIZE as usize + CHANGELOG_ENTRY_P1_OFFSET;
				buf.copy_from_slice(&changelog[offset..offset + 8]);
				transmute(buf)
				};
				(revs[0].to_be(), revs[1].to_be())
				}

				fn insert(radix_buf: &mut Vec<u32>, key_buf: &mut Vec<u32>, offset: u32, parent: i32, child: i32)
				-> Result<()> {
				assert_ne!(parent, child);
				// Find the existing slot of child. Creat an entry on demand.
				let key = rev_to_key(parent);
				let existing = radix_lookup(radix_buf, offset, &key, &key_reader, &key_buf)?;
				let offset: u32 = match existing {
				Some(v) => v.into(),
				None => {
				let key_id = append_linked_node(key_buf, parent, 0);
				radix_insert_with_key(radix_buf, offset, key_id.into(), &key, &key_reader, key_buf)?;
				key_id
				}
				};

				// Insert the parent to the linked list.
				//
				// Before: After:
				//
				// key_id (offset) key_id (offset) pos
				// v v v
				// +---------------+ +---------------+ +--------------+
				// \| parent \| next \| \| parent \| new \| \| child \| next \|
				// +---------------+ +-----------v---+ +---^----------+
				// \| \|
				// +----------+
				if offset as usize + 1 >= key_buf.len() {
				bail!(ErrorKind::IndexCorrupted)
				}
				let next = u32::from_be(key_buf[offset as usize + 1]);
				let pos = append_linked_node(key_buf, child, next);
				key_buf[offset as usize + 1] = pos.to_be();

				Ok(())
				}

				/// Read parent revs from radix index -> linked list. Append them to result.
				fn lookup<R, K>(radix_buf: &R, key_buf: &K, offset: u32, parent: i32, result: &mut Vec<i32>)
				-> Result<()>
				where
				R: AsRef<[u32]>,
				K: AsRef<[u32]>,
				{
				let key = rev_to_key(parent);
				let radix_buf = radix_buf.as_ref();
				let key_buf = key_buf.as_ref();
				match radix_lookup(&radix_buf, offset, &key, &key_reader, &key_buf)? {
				Some(id) => {
				// Read the linked list from key_buf
				let mut offset: usize = id.into();
				while offset != 0 {
				if offset + 1 > key_buf.as_ref().len() {
				bail!(ErrorKind::IndexCorrupted);
				}
				let new_parent = i32::from_be(key_buf[offset] as i32);
				let next = u32::from_be(key_buf[offset + 1]);
				if new_parent != parent {
				result.push(new_parent);
				}
				offset = next as usize;
				}
				Ok(())
				}
				None => Ok(()),
				}
				}

				/// Read parent -> child relationships for parent in xrange(start_rev, end_rev) from changelog,
				/// insert them to the radix index.
				fn build(
				changelog: &[u8], radix_buf: &mut Vec<u32>, key_buf: &mut Vec<u32>, offset: u32, start_rev: u32,
				end_rev: u32
				) -> Result<()> {
				for i in start_rev..end_rev {
				let (p1, p2) = parents(changelog, i);
				// Skip "parent + 1 == child" case to save space.
				if p1 + 1 != i as i32 {
				insert(radix_buf, key_buf, offset, p1, i as i32)?;
				}
				if p2 >= 0 && p2 + 1 != i as i32 {
				insert(radix_buf, key_buf, offset, p2, i as i32)?;
				}
				}
				Ok(())
				}

				/// Append (rev: u32, next_offset: u32) to the key buffer. Return the offset of rev.
				fn append_linked_node(key_buf: &mut Vec<u32>, rev: i32, next: u32) -> u32 {
				let pos = key_buf.len() as u64;
				assert!(pos < 0xffff_ffff);
				key_buf.push(rev.to_be() as u32);
				key_buf.push(next.to_be());
				pos as u32
				}

				/// Read fixed 4-byte sequence from key buffer
				fn key_reader<K: AsRef<[u32]>>(key_buf: &K, key_id: KeyId) -> rerrors::Result<&[u8]> {
				let key_buf = key_buf.as_ref();
				let start_pos: usize = key_id.into();
				let end_pos = start_pos + 1;
				if key_buf.len() < end_pos {
				bail!(rerrors::ErrorKind::InvalidKeyId(key_id));
				}
				let result = &key_buf[start_pos..end_pos];
				// Cast [u32] to [u8]
				Ok(&unsafe {
				slice::from_raw_parts(result.as_ptr() as *const u8, 4)
				})
				}

				/// Convert revision number to a key ([u8])
				fn rev_to_key(rev: i32) -> [u8; 4] { unsafe { transmute(rev.to_be()) } }

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

				#[test]
				fn test_manual_case() {
				let mut changelogi: Vec<u8> = vec![];
				let empty_index = ChildRevMap::<Vec<u8>, Vec<u32>>::empty_index_buffer();
				{
				// Take a snapshot of empty changelog.i and do some tests.
				let changelogi = changelogi.clone();
				let map = ChildRevMap::new(&changelogi, empty_index.clone()).unwrap();
				assert_eq!(map.lag(), 0);
				assert_eq!(map.build_incrementally().unwrap(), empty_index.clone());
				}

				// Insert 2 revisions:
				// 1 2
				// \|/
				// 0
				let mut index_partial: Vec<u32> = vec![];
				append_changelog(&mut changelogi, 0, -1, -1);
				append_changelog(&mut changelogi, 1, 0, -1);
				append_changelog(&mut changelogi, 2, 0, -1);
				{
				let changelogi = changelogi.clone();
				let map1 = ChildRevMap::new(&changelogi, empty_index.clone()).unwrap();
				let index = map1.build_incrementally().unwrap();
				index_partial.extend(index.clone()); // used by the next test
				let map2 = ChildRevMap::new(&changelogi, index).unwrap();

				assert_eq!(map1.lag(), 3);
				assert_eq!(map2.lag(), 0);
				for map in [&map1, &map2].iter() {
				assert_eq!(map.lookup(-1).unwrap(), vec![0]);
				assert_eq!(map.lookup(0).unwrap(), vec![1, 2]);
				assert_eq!(map.lookup(1).unwrap(), vec![]);
				assert_eq!(map.lookup(2).unwrap(), vec![]);
				assert_eq!(map.lookup(3).unwrap(), vec![]);
				}
				}

				// Insert more revisions:
				// 6 7 5
				// \|\\|\ \|
				// 1 2 3 4
				// \\|/ /
				// \|/
				// 0 8
				append_changelog(&mut changelogi, 3, 0, -1);
				append_changelog(&mut changelogi, 4, 0, -1);
				append_changelog(&mut changelogi, 5, 4, -1);
				append_changelog(&mut changelogi, 6, 1, 2);
				append_changelog(&mut changelogi, 7, 2, 3);
				append_changelog(&mut changelogi, 8, -1, -1);
				{
				let changelogi = changelogi.clone();

				// build from scratch
				let map_from_scratch = ChildRevMap::new(&changelogi, empty_index.clone()).unwrap();

				// build incrementally from a childmap with 3 revisions
				let map_from_partial = ChildRevMap::new(&changelogi, index_partial).unwrap();

				let index_complete = map_from_scratch.build_incrementally().unwrap();
				assert_eq!(
				index_complete,
				map_from_partial.build_incrementally().unwrap()
				);

				// build from an up-to-date childmap
				let map_from_complete = ChildRevMap::new(&changelogi, index_complete).unwrap();

				assert_eq!(map_from_scratch.lag(), 9);
				assert_eq!(map_from_partial.lag(), 6);
				assert_eq!(map_from_complete.lag(), 0);
				for map in [&map_from_scratch, &map_from_partial, &map_from_complete].iter() {
				assert_eq!(map.lookup(-1).unwrap(), vec![0, 8]);
				assert_eq!(map.lookup(0).unwrap(), vec![1, 2, 3, 4]);
				assert_eq!(map.lookup(1).unwrap(), vec![6]);
				assert_eq!(map.lookup(2).unwrap(), vec![6, 7]);
				assert_eq!(map.lookup(3).unwrap(), vec![7]);
				assert_eq!(map.lookup(4).unwrap(), vec![5]);
				assert_eq!(map.lookup(5).unwrap(), vec![]);
				assert_eq!(map.lookup(6).unwrap(), vec![]);
				assert_eq!(map.lookup(7).unwrap(), vec![]);
				assert_eq!(map.lookup(8).unwrap(), vec![]);
				assert_eq!(map.lookup(9).unwrap(), vec![]);
				}
				}
				}

				fn append_changelog(changelogi: &mut Vec<u8>, rev: u32, p1: i32, p2: i32) {
				assert_eq!(
				rev as usize,
				changelogi.len() / CHANGELOG_ENTRY_SIZE as usize
				);
				let mut entry = [0u8; CHANGELOG_ENTRY_SIZE as usize];
				let p1buf: [u8; 4] = unsafe { transmute(p1.to_be()) };
				let p2buf: [u8; 4] = unsafe { transmute(p2.to_be()) };
				entry[24..28].copy_from_slice(&p1buf);
				entry[28..32].copy_from_slice(&p2buf);
				changelogi.extend_from_slice(&entry);
				}
				}

rust/indexes/src/lib.rs

	// Copyright 2017 Facebook, Inc.			// Copyright 2017 Facebook, Inc.
	//			//
	// This software may be used and distributed according to the terms of the			// This software may be used and distributed according to the terms of the
	// GNU General Public License version 2 or any later version.			// GNU General Public License version 2 or any later version.

	extern crate python27_sys;			extern crate python27_sys;

	#[macro_use]			#[macro_use]
	extern crate cpython;			extern crate cpython;
	#[macro_use]			#[macro_use]
	extern crate error_chain;			extern crate error_chain;
	extern crate radixbuf;			extern crate radixbuf;

	pub mod errors;			pub mod errors;
				pub mod childmap;
	pub mod nodemap;			pub mod nodemap;
	mod changelog_utils;			mod changelog_utils;
	mod pybuf;			mod pybuf;

	#[allow(non_camel_case_types)]			#[allow(non_camel_case_types)]
	pub mod pyext;			pub mod pyext;

rust/indexes/src/pyext.rs

	// Copyright 2017 Facebook, Inc.			// Copyright 2017 Facebook, Inc.
	//			//
	// This software may be used and distributed according to the terms of the			// This software may be used and distributed according to the terms of the
	// GNU General Public License version 2 or any later version.			// GNU General Public License version 2 or any later version.

	use cpython::{PyResult, PyBytes, PyObject};			use childmap::ChildRevMap;
				use cpython::{PyResult, PyBytes, PyObject, PyInt};
	use nodemap::NodeRevMap;			use nodemap::NodeRevMap;
	use pybuf::SimplePyBuf;			use pybuf::SimplePyBuf;
	use std::slice;			use std::slice;

	py_module_initializer!(indexes, initindexes, PyInit_indexes, \|py, m\| {			py_module_initializer!(indexes, initindexes, PyInit_indexes, \|py, m\| {
	try!(m.add_class::<nodemap>(py));			try!(m.add_class::<nodemap>(py));
				try!(m.add_class::<childmap>(py));
	Ok(())			Ok(())
	});			});

	py_class!(class nodemap \|py\| {			py_class!(class nodemap \|py\| {
	data nodemap: NodeRevMap<SimplePyBuf<u8>, SimplePyBuf<u32>>;			data nodemap: NodeRevMap<SimplePyBuf<u8>, SimplePyBuf<u32>>;

	def __new__(_cls, changelog: &PyObject, index: &PyObject) -> PyResult<nodemap> {			def __new__(_cls, changelog: &PyObject, index: &PyObject) -> PyResult<nodemap> {
	let changelog_buf = SimplePyBuf::new(py, changelog);			let changelog_buf = SimplePyBuf::new(py, changelog);

	@staticmethod			@staticmethod
	def emptyindexbuffer() -> PyResult<PyBytes> {			def emptyindexbuffer() -> PyResult<PyBytes> {
	let buf = NodeRevMap::<Vec<u8>, Vec<u32>>::empty_index_buffer();			let buf = NodeRevMap::<Vec<u8>, Vec<u32>>::empty_index_buffer();
	let slice = unsafe { slice::from_raw_parts(buf.as_ptr() as const u8, buf.len() 4) };			let slice = unsafe { slice::from_raw_parts(buf.as_ptr() as const u8, buf.len() 4) };
	Ok(PyBytes::new(py, slice))			Ok(PyBytes::new(py, slice))
	}			}
	});			});

				py_class!(class childmap \|py\| {
				data childmap: ChildRevMap<SimplePyBuf<u8>, SimplePyBuf<u32>>;

				def __new__(_cls, changelog: &PyObject, index: &PyObject) -> PyResult<childmap> {;
				let changelog_buf = SimplePyBuf::new(py, changelog);
				let index_buf = SimplePyBuf::new(py, index);
				let map = ChildRevMap::new(changelog_buf, index_buf)?;
				childmap::create_instance(py, map)
				}

				def __getitem__(&self, rev: i32) -> PyResult<Vec<i32>> {
				Ok(self.childmap(py).lookup(rev)?)
				}

				def parentrevs(&self, rev: PyInt) -> PyResult<Option<(i32, i32)>> {
				let revs = self.childmap(py).parentrevs(rev.value(py) as u32);
				Ok(revs)
				}

				def build(&self) -> PyResult<PyBytes> {
				let buf = self.childmap(py).build_incrementally()?;
				let slice = unsafe { slice::from_raw_parts(buf.as_ptr() as const u8, buf.len() 4) };
				Ok(PyBytes::new(py, slice))
				}

				def lag(&self) -> PyResult<u32> {
				Ok(self.childmap(py).lag())
				}

				@staticmethod
				def emptyindexbuffer() -> PyResult<PyBytes> {
				let buf = ChildRevMap::<Vec<u8>, Vec<u32>>::empty_index_buffer();
				let slice = unsafe { slice::from_raw_parts(buf.as_ptr() as const u8, buf.len() 4) };
				Ok(PyBytes::new(py, slice))
				}
				});

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	3881		Nov 27 2017, 1:30 PM	★	★
Diff 2	4456		Dec 14 2017, 9:21 PM	★	★
Diff 3	4462		Dec 14 2017, 10:15 PM	★	★

This is an archive of the discontinued Mercurial Phabricator instance.

childmap: add a map for efficient children queryAbandonedPublic

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 4462

rust/indexes/src/childmap.rs

rust/indexes/src/lib.rs

rust/indexes/src/pyext.rs

childmap: add a map for efficient children query
AbandonedPublic

Revision Contents
Changeset List