This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1292

radix204: implement prefix lookup
AbandonedPublic

Authored by quark on Nov 2 2017, 2:45 PM.
Tags
None
Subscribers
None

Details

Reviewers
None
Group Reviewers
Restricted Project
Summary

The prefix lookup feature is used in sourcecontrol where the user provides an
incomplete hex string asking for the full commit hash. This diff implements it.

Test Plan

cargo test --lib. Also check kcov report to make sure every line in
lookup_prefix is covered.

Diff Detail

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

Event Timeline

quark created this revision.Nov 2 2017, 2:45 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 2 2017, 2:45 PM
quark updated this revision to Diff 3252.Nov 3 2017, 2:17 AM
quark edited the summary of this revision. (Show Details)Nov 6 2017, 2:10 PM
quark updated this revision to Diff 3297.
quark abandoned this revision.Nov 11 2017, 1:34 AM

This becomes shorter after some refactoring. Therefore folded to a previous patch.

Revision Contents
Changeset List

Diff 3297

rust/radix204/src/errors.rs

} }
KeyConflict { KeyConflict {
description("same key with different IDs") description("same key with different IDs")
} }
KeyIncomplete(key_id: KeyId) { KeyIncomplete(key_id: KeyId) {
description("incomplete key") description("incomplete key")
display("key (id={}) is incomplete", key_id.to_usize()) display("key (id={}) is incomplete", key_id.to_usize())
} }
AmbiguousPrefix {
description("ambiguous prefix")
}
} }
} }

rust/radix204/src/radix.rs

Ok(FollowResult::KeyId((v >> 1).into())) Ok(FollowResult::KeyId((v >> 1).into()))
} else { } else {
Ok(FollowResult::Radix(RadixNode::new(v.into()))) Ok(FollowResult::Radix(RadixNode::new(v.into())))
} }
} }
} }
} }
/// Return an iterator of non-none (not 0) indexes.
#[inline]
pub fn keys(&self, vec: &mut RB) -> Result<Vec<u8>> {
let pos = self.0.to_usize();
let end = pos + 16;
if end > vec.len() {
return Err(ErrorKind::OffsetOverflow(pos).into());
}
Ok(
vec[pos..end]
.iter()
.enumerate()
.filter(|&(_, v)| *v != 0)
.map(|(i, _)| i as u8)
.collect(),
)
}
/// Rewrite an index entry to point to another `RadixNode`. /// Rewrite an index entry to point to another `RadixNode`.
#[inline] #[inline]
pub fn write_radix(&self, vec: &mut RB, index: u8, node: &RadixNode) -> Result<()> { pub fn write_radix(&self, vec: &mut RB, index: u8, node: &RadixNode) -> Result<()> {
self.write_raw_offset(vec, index, node.0) self.write_raw_offset(vec, index, node.0)
} }
/// Rewrite an index entry to point to a `KeyId`. /// Rewrite an index entry to point to a `KeyId`.
#[inline] #[inline]
} }
FollowResult::KeyId(id) => return Ok(Some(id)), FollowResult::KeyId(id) => return Ok(Some(id)),
} }
} }
Err(ErrorKind::KeyConflict.into()) Err(ErrorKind::KeyConflict.into())
}) })
} }
pub fn lookup_prefix(&self, base16seq: &[u8]) -> Result<Option<KeyId>> {
borrow_shared(&self.1, |rbuf| {
let mut radix = RadixNode::new(self.2);
for &b in base16seq {
debug_assert!(b < 16);
match radix.follow(rbuf, b)? {
FollowResult::Radix(next_radix) => {
radix = next_radix;
}
FollowResult::Missing => {
return Ok(None);
}
FollowResult::KeyId(id) => {
let key = self.read_key(id)?;
let matched = key.to_base16iter().zip(base16seq.iter()).all(|(b1, &b2)| {
b1 == b2
});
return if key.len() * 2 >= base16seq.len() && matched {
Ok(Some(id))
} else {
Ok(None)
};
}
}
}
loop {
let keys = radix.keys(rbuf)?;
match keys.len() {
0 => return Ok(None),
1 => {
match radix.follow(rbuf, keys[0])? {
FollowResult::Radix(next_radix) => {
radix = next_radix;
}
FollowResult::Missing => {
return Ok(None);
}
FollowResult::KeyId(id) => return Ok(Some(id)),
}
}
_ => return Err(ErrorKind::AmbiguousPrefix.into()),
}
}
})
}
/// Insert when `KeyId` is known /// Insert when `KeyId` is known
pub fn insert(&self, new_key_id: KeyId) -> Result<()> { pub fn insert(&self, new_key_id: KeyId) -> Result<()> {
let new_key = self.read_key(new_key_id)?; let new_key = self.read_key(new_key_id)?;
self.insert_with_key(new_key_id, &new_key) self.insert_with_key(new_key_id, &new_key)
} }
/// Insert when both `KeyId` and `Key` are known /// Insert when both `KeyId` and `Key` are known
pub fn insert_with_key(&self, new_key_id: KeyId, new_key: &Key) -> Result<()> { pub fn insert_with_key(&self, new_key_id: KeyId, new_key: &Key) -> Result<()> {
let r = radix.insert_with_key((1 << 31).into(), &key); let r = radix.insert_with_key((1 << 31).into(), &key);
assert_eq!(r.unwrap_err().description(), "offset overflow"); assert_eq!(r.unwrap_err().description(), "offset overflow");
assert_eq!( assert_eq!(
radix.insert(1.into()).unwrap_err().description(), radix.insert(1.into()).unwrap_err().description(),
"incomplete key" "incomplete key"
); );
} }
#[test]
fn test_lookup_prefix() {
let (kbuf, _rbuf, radix) = prepare_kbuf_radix();
assert_eq!(radix.lookup_prefix(&[0x1]).unwrap(), None);
let key = b"0123456789abcdefghij".into();
let key_id = append_key(&kbuf, &key);
radix.insert(key_id).expect("insert");
let base16: Vec<u8> = key.to_base16iter()
.chain([0u8; 10].iter().cloned())
.collect();
for i in 0..base16.len() {
let r = radix.lookup_prefix(&base16[0..i]).unwrap();
if i <= 40 {
assert_eq!(r, Some(key_id));
} else {
assert_eq!(r, None);
}
}
let key = b"0123456789bbcdefghij".into();
radix.insert(append_key(&kbuf, &key)).expect("insert");
for i in 0..base16.len() {
let r = radix.lookup_prefix(&base16[0..i]);
if i <= 21 {
assert_eq!(r.unwrap_err().description(), "ambiguous prefix")
} else if i <= 40 {
assert_eq!(r.unwrap(), Some(key_id));
} else {
assert_eq!(r.unwrap(), None);
}
}
}
#[bench] #[bench]
fn bench_50k_insert(b: &mut Bencher) { fn bench_50k_insert(b: &mut Bencher) {
const COUNT: u32 = 51200; const COUNT: u32 = 51200;
let key_buf: Vec<u8> = ChaChaRng::new_unseeded() let key_buf: Vec<u8> = ChaChaRng::new_unseeded()
.gen_iter() .gen_iter()
.take(COUNT as usize * Key::fixed_len()) .take(COUNT as usize * Key::fixed_len())
.collect(); .collect();
let kbuf = Rc::new(RefCell::new(key_buf)); let kbuf = Rc::new(RefCell::new(key_buf));