( )⚙ D1519 childmap: add a map for efficient children query

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1519

childmap: add a map for efficient children query
AbandonedPublic

Authored by quark on Nov 27 2017, 1:30 PM.
Tags
None
Subscribers
kevincox

Details

Reviewers
None
Group Reviewers
Restricted Project
Summary

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

quark created this revision.Nov 27 2017, 1:30 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 27 2017, 1:30 PM
quark updated this revision to Diff 4456.Dec 14 2017, 9:21 PM
quark updated this revision to Diff 4462.Dec 14 2017, 10:15 PM
quark abandoned this revision.Dec 7 2019, 2:13 AM

Revision Contents
Changeset List

Diff 3881

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 radixbuf::key::{KeyId, FixedKey};
use radixbuf::radix::{KeyReader, radix_lookup, radix_insert_with_key};
use radixbuf::errors as rerrors;
use utils::{changelog_next_rev, rev_to_node};
/// An index with rev -> a list of rev mapping intended for storing children.
/// Use revision numbers to make the index compact. But insertion order does not have to be
/// topo-sorted.
pub struct ChildRevMap<C, I> {
changelog: C,
end_rev: u32,
main_index: I, // Immutable main index
side_index: Vec<u32>, // Mutable side index
}
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(changelog: C, main_index: I) -> Result<Self> {
// Sanity check. Like NodeRevMap.
// The index must contain at least 22 elements. index[1..6] tracks the last node. index[0]
// tracks the last rev. index[6..6+16] tracks the radix node.
if main_index.as_ref().len() < 22 {
bail!(ErrorKind::IndexCorrupted);
}
// Check if the index is behind and build incrementally
let next_rev = main_index.as_ref()[0].to_le();
let end_rev = changelog_next_rev(&changelog);
if next_rev > end_rev {
bail!(ErrorKind::IndexCorrupted);
} else if next_rev > 0 {
let node_index: [u8; 20] = unsafe {
let mut buf = [0u32; 5];
buf.copy_from_slice(&main_index.as_ref()[1..6]);
transmute(buf)
};
let node_changelog = rev_to_node(changelog.as_ref(), (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];
build(changelog.as_ref(), &mut side_index, 0, next_rev, end_rev)?;
Ok(ChildRevMap {
changelog,
end_rev,
main_index,
side_index,
})
}
// 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.changelog.as_ref(), rev))
}
}
pub fn lookup(&self, rev: u32) -> Result<Vec<u32>> {
let mut childrevs = Vec::with_capacity(1);
// Combine both indexes
lookup(&self.main_index.as_ref(), 6, rev, &mut childrevs)?;
lookup(&self.side_index, 0, rev, &mut childrevs)?;
// Common case
if rev + 1 < self.end_rev {
let (p1, p2) = self.parentrevs(rev + 1).unwrap();
if (p1 >= 0 && p1 as u32 == rev) || (p2 >= 0 && p2 as u32 == rev) {
childrevs.push(rev + 1)
}
}
Ok(childrevs)
}
/// How many revisions the side index has.
pub fn lag(&self) -> u32 {
let next_rev = self.main_index.as_ref()[0].to_le();
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 mut index = self.main_index.as_ref().to_vec();
let next_rev = index[0].to_le();
let cl = self.changelog.as_ref();
build(cl, &mut index, 6, next_rev, self.end_rev)?;
// Rewrite header
index[0] = self.end_rev.to_le();
if self.end_rev > 0 {
let offset = self.end_rev * 64 - 32;
let node = FixedKey::read(self.changelog.as_ref(), offset.into())?;
let mut buf = [0u8; 20];
buf.copy_from_slice(&node);
let buf: [u32; 5] = unsafe {transmute(buf)};
index[1..6].copy_from_slice(&buf);
}
Ok(index)
}
}
#[inline]
fn parents(changelog: &[u8], rev: u32) -> (i32, i32) {
let revs: [i32; 2] = unsafe {
let mut buf = [0u8; 8];
let offset = rev as usize * 64 + 24;
buf.copy_from_slice(&changelog[offset..offset + 8]);
transmute(buf)
};
(revs[0].to_be(), revs[1].to_be())
}
#[inline]
fn insert(index: &mut Vec<u32>, offset: u32, parent: u32, child: u32) -> Result<()> {
assert_ne!(parent, child);
// Find the existing slot of child.
let key_reader = KeyReader::RadixBufferAllocated(read_key);
let key = rev_to_buf(parent);
let existing = radix_lookup(index, offset, &key, &key_reader)?;
let offset: u32 = match existing {
Some(v) => v.into(),
None => {
let key_id = append_node(index, parent, 0);
radix_insert_with_key(index, offset, key_id.into(), &key, &key_reader)?;
key_id
}
}.to_le();
// Insert the parent to the linked list.
//
// Before: After:
//
// key_id (offset) key_id (unchanged)
// v v
// +---------------+ +---------------+ +--------------+
// | parent | next | | parent | new | | child | next |
// +---------------+ +---------------+ +---^----------+
// | |
// +-----------------+
//
if offset as usize + 1 >= index.len() {
bail!(ErrorKind::IndexCorrupted)
}
let next = index[offset as usize + 1].to_le();
let pos = append_node(index, child, next);
index[offset as usize + 1] = pos.to_le();
Ok(())
}
#[inline]
fn lookup(index: &[u32], offset: u32, parent: u32, result: &mut Vec<u32>) -> Result<()> {
let key_reader = KeyReader::RadixBufferAllocated(read_key);
let key = rev_to_buf(parent);
match radix_lookup(&index, offset, &key, &key_reader)? {
Some(id) => {
let mut offset: usize = id.into();
while offset != 0 {
if offset + 1 > index.len() {
bail!(ErrorKind::IndexCorrupted);
}
let new_parent = index[offset].to_le();
let next = index[offset + 1].to_le();
if new_parent != parent {
result.push(new_parent);
}
offset = next as usize;
}
Ok(())
}
None => Ok(()),
}
}
fn build(changelog: &[u8], index: &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 >= 0 && p1 + 1 != i as i32 {
insert(index, offset, p1 as u32, i)?;
}
if p2 >= 0 && p2 + 1 != i as i32 {
insert(index, offset, p2 as u32, i)?;
}
}
Ok(())
}
/// Append (rev: u32, next_offset: u32) to the buffer. Return the offset of rev.
fn append_node(buf: &mut Vec<u32>, rev: u32, next: u32) -> u32 {
let pos = buf.len() as u64;
assert!(pos < 0xffff_ffff);
buf.push(rev.to_le());
buf.push(next.to_le());
pos as u32
}
fn read_key(radix_buf: &[u32], key_id: KeyId) -> rerrors::Result<Box<[u8]>> {
// `key_id` is a pointer
let offset: usize = key_id.into();
if offset >= radix_buf.len() {
bail!(rerrors::ErrorKind::InvalidKeyId(key_id))
}
let rev = radix_buf[offset].to_le();
Ok(rev_to_buf(rev))
}
#[inline]
fn rev_to_buf(rev: u32) -> Box<[u8]> {
let buf: [u8; 4] = unsafe { transmute(rev.to_le()) };
buf.to_vec().into_boxed_slice()
}

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 utils; mod 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);
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))
} }
def lag(&self) -> PyResult<u32> { def lag(&self) -> PyResult<u32> {
Ok(self.nodemap(py).lag()) Ok(self.nodemap(py).lag())
} }
}); });
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: u32) -> PyResult<Vec<u32>> {
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())
}
});