rust-index-cpython: cache the heads' PyList representation

This is the same optimization that the C index does, we just have more
separation of the Python and native sides.

rust/hg-core/src/revlog/index.rs

@@ -1,2009 +1,2024 b''
 use std::collections::{HashMap, HashSet};
 use std::fmt::Debug;
 use std::ops::Deref;
 use std::sync::{RwLock, RwLockReadGuard, RwLockWriteGuard};
 
 use bitvec::prelude::*;
 use byteorder::{BigEndian, ByteOrder};
 use bytes_cast::{unaligned, BytesCast};
 
 use super::REVIDX_KNOWN_FLAGS;
 use crate::errors::HgError;
 use crate::node::{NODE_BYTES_LENGTH, NULL_NODE, STORED_NODE_ID_BYTES};
 use crate::revlog::node::Node;
 use crate::revlog::{Revision, NULL_REVISION};
 use crate::{
     dagops, BaseRevision, FastHashMap, Graph, GraphError, RevlogError,
     RevlogIndex, UncheckedRevision,
 };
 
 pub const INDEX_ENTRY_SIZE: usize = 64;
 pub const COMPRESSION_MODE_INLINE: u8 = 2;
 
 #[derive(Debug)]
 pub struct IndexHeader {
     pub(super) header_bytes: [u8; 4],
 }
 
 #[derive(Copy, Clone)]
 pub struct IndexHeaderFlags {
     flags: u16,
 }
 
 /// Corresponds to the high bits of `_format_flags` in python
 impl IndexHeaderFlags {
     /// Corresponds to FLAG_INLINE_DATA in python
     pub fn is_inline(self) -> bool {
         self.flags & 1 != 0
     }
     /// Corresponds to FLAG_GENERALDELTA in python
     pub fn uses_generaldelta(self) -> bool {
         self.flags & 2 != 0
     }
 }
 
 /// Corresponds to the INDEX_HEADER structure,
 /// which is parsed as a `header` variable in `_loadindex` in `revlog.py`
 impl IndexHeader {
     fn format_flags(&self) -> IndexHeaderFlags {
         // No "unknown flags" check here, unlike in python. Maybe there should
         // be.
         IndexHeaderFlags {
             flags: BigEndian::read_u16(&self.header_bytes[0..2]),
         }
     }
 
     /// The only revlog version currently supported by rhg.
     const REVLOGV1: u16 = 1;
 
     /// Corresponds to `_format_version` in Python.
     fn format_version(&self) -> u16 {
         BigEndian::read_u16(&self.header_bytes[2..4])
     }
 
     pub fn parse(index_bytes: &[u8]) -> Result<Option<IndexHeader>, HgError> {
         if index_bytes.is_empty() {
             return Ok(None);
         }
         if index_bytes.len() < 4 {
             return Err(HgError::corrupted(
                 "corrupted revlog: can't read the index format header",
             ));
         }
         Ok(Some(IndexHeader {
             header_bytes: {
                 let bytes: [u8; 4] =
                     index_bytes[0..4].try_into().expect("impossible");
                 bytes
             },
         }))
     }
 }
 
 /// Abstracts the access to the index bytes since they can be spread between
 /// the immutable (bytes) part and the mutable (added) part if any appends
 /// happened. This makes it transparent for the callers.
 struct IndexData {
     /// Immutable bytes, most likely taken from disk
     bytes: Box<dyn Deref<Target = [u8]> + Send + Sync>,
     /// Used when stripping index contents, keeps track of the start of the
     /// first stripped revision, which is used to give a slice of the
     /// `bytes` field.
     truncation: Option<usize>,
     /// Bytes that were added after reading the index
     added: Vec<u8>,
 }
 
 impl IndexData {
     pub fn new(bytes: Box<dyn Deref<Target = [u8]> + Send + Sync>) -> Self {
         Self {
             bytes,
             truncation: None,
             added: vec![],
         }
     }
 
     pub fn len(&self) -> usize {
         match self.truncation {
             Some(truncation) => truncation + self.added.len(),
             None => self.bytes.len() + self.added.len(),
         }
     }
 
     fn remove(
         &mut self,
         rev: Revision,
         offsets: Option<&[usize]>,
     ) -> Result<(), RevlogError> {
         let rev = rev.0 as usize;
         let truncation = if let Some(offsets) = offsets {
             offsets[rev]
         } else {
             rev * INDEX_ENTRY_SIZE
         };
         if truncation < self.bytes.len() {
             self.truncation = Some(truncation);
             self.added.clear();
         } else {
             self.added.truncate(truncation - self.bytes.len());
         }
         Ok(())
     }
 
     fn is_new(&self) -> bool {
         self.bytes.is_empty()
     }
 }
 
 impl std::ops::Index<std::ops::Range<usize>> for IndexData {
     type Output = [u8];
 
     fn index(&self, index: std::ops::Range<usize>) -> &Self::Output {
         let start = index.start;
         let end = index.end;
         let immutable_len = match self.truncation {
             Some(truncation) => truncation,
             None => self.bytes.len(),
         };
         if start < immutable_len {
             if end > immutable_len {
                 panic!("index data cannot span existing and added ranges");
             }
             &self.bytes[index]
         } else {
             &self.added[start - immutable_len..end - immutable_len]
         }
     }
 }
 
 #[derive(Debug, PartialEq, Eq)]
 pub struct RevisionDataParams {
     pub flags: u16,
     pub data_offset: u64,
     pub data_compressed_length: i32,
     pub data_uncompressed_length: i32,
     pub data_delta_base: i32,
     pub link_rev: i32,
     pub parent_rev_1: i32,
     pub parent_rev_2: i32,
     pub node_id: [u8; NODE_BYTES_LENGTH],
     pub _sidedata_offset: u64,
     pub _sidedata_compressed_length: i32,
     pub data_compression_mode: u8,
     pub _sidedata_compression_mode: u8,
     pub _rank: i32,
 }
 
 impl Default for RevisionDataParams {
     fn default() -> Self {
         Self {
             flags: 0,
             data_offset: 0,
             data_compressed_length: 0,
             data_uncompressed_length: 0,
             data_delta_base: -1,
             link_rev: -1,
             parent_rev_1: -1,
             parent_rev_2: -1,
             node_id: [0; NODE_BYTES_LENGTH],
             _sidedata_offset: 0,
             _sidedata_compressed_length: 0,
             data_compression_mode: COMPRESSION_MODE_INLINE,
             _sidedata_compression_mode: COMPRESSION_MODE_INLINE,
             _rank: -1,
         }
     }
 }
 
 #[derive(BytesCast)]
 #[repr(C)]
 pub struct RevisionDataV1 {
     data_offset_or_flags: unaligned::U64Be,
     data_compressed_length: unaligned::I32Be,
     data_uncompressed_length: unaligned::I32Be,
     data_delta_base: unaligned::I32Be,
     link_rev: unaligned::I32Be,
     parent_rev_1: unaligned::I32Be,
     parent_rev_2: unaligned::I32Be,
     node_id: [u8; STORED_NODE_ID_BYTES],
 }
 
 fn _static_assert_size_of_revision_data_v1() {
     let _ = std::mem::transmute::<RevisionDataV1, [u8; 64]>;
 }
 
 impl RevisionDataParams {
     pub fn validate(&self) -> Result<(), RevlogError> {
         if self.flags & !REVIDX_KNOWN_FLAGS != 0 {
             return Err(RevlogError::corrupted(format!(
                 "unknown revlog index flags: {}",
                 self.flags
             )));
         }
         if self.data_compression_mode != COMPRESSION_MODE_INLINE {
             return Err(RevlogError::corrupted(format!(
                 "invalid data compression mode: {}",
                 self.data_compression_mode
             )));
         }
         // FIXME isn't this only for v2 or changelog v2?
         if self._sidedata_compression_mode != COMPRESSION_MODE_INLINE {
             return Err(RevlogError::corrupted(format!(
                 "invalid sidedata compression mode: {}",
                 self._sidedata_compression_mode
             )));
         }
         Ok(())
     }
 
     pub fn into_v1(self) -> RevisionDataV1 {
         let data_offset_or_flags = self.data_offset << 16 | self.flags as u64;
         let mut node_id = [0; STORED_NODE_ID_BYTES];
         node_id[..NODE_BYTES_LENGTH].copy_from_slice(&self.node_id);
         RevisionDataV1 {
             data_offset_or_flags: data_offset_or_flags.into(),
             data_compressed_length: self.data_compressed_length.into(),
             data_uncompressed_length: self.data_uncompressed_length.into(),
             data_delta_base: self.data_delta_base.into(),
             link_rev: self.link_rev.into(),
             parent_rev_1: self.parent_rev_1.into(),
             parent_rev_2: self.parent_rev_2.into(),
             node_id,
         }
     }
 }
 
 /// A Revlog index
 pub struct Index {
     bytes: IndexData,
     /// Offsets of starts of index blocks.
     /// Only needed when the index is interleaved with data.
     offsets: RwLock<Option<Vec<usize>>>,
     uses_generaldelta: bool,
     is_inline: bool,
     /// Cache of (head_revisions, filtered_revisions)
     ///
     /// The head revisions in this index, kept in sync. Should
     /// be accessed via the [`Self::head_revs`] method.
     /// The last filtered revisions in this index, used to make sure
     /// we haven't changed filters when returning the cached `head_revs`.
     head_revs: RwLock<(Vec<Revision>, HashSet<Revision>)>,
 }
 
 impl Debug for Index {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         f.debug_struct("Index")
             .field("offsets", &self.offsets)
             .field("uses_generaldelta", &self.uses_generaldelta)
             .finish()
     }
 }
 
 impl Graph for Index {
     #[inline(always)]
     fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
         let err = || GraphError::ParentOutOfRange(rev);
         match self.get_entry(rev) {
             Some(entry) => {
                 // The C implementation checks that the parents are valid
                 // before returning
                 Ok([
                     self.check_revision(entry.p1()).ok_or_else(err)?,
                     self.check_revision(entry.p2()).ok_or_else(err)?,
                 ])
             }
             None => Ok([NULL_REVISION, NULL_REVISION]),
         }
     }
 }
 
 /// A cache suitable for find_snapshots
 ///
 /// Logically equivalent to a mapping whose keys are [`BaseRevision`] and
 /// values sets of [`BaseRevision`]
 ///
 /// TODO the dubious part is insisting that errors must be RevlogError
 /// we would probably need to sprinkle some magic here, such as an associated
 /// type that would be Into<RevlogError> but even that would not be
 /// satisfactory, as errors potentially have nothing to do with the revlog.
 pub trait SnapshotsCache {
     fn insert_for(
         &mut self,
         rev: BaseRevision,
         value: BaseRevision,
     ) -> Result<(), RevlogError>;
 }
 
 impl SnapshotsCache for FastHashMap<BaseRevision, HashSet<BaseRevision>> {
     fn insert_for(
         &mut self,
         rev: BaseRevision,
         value: BaseRevision,
     ) -> Result<(), RevlogError> {
         let all_values = self.entry(rev).or_insert_with(HashSet::new);
         all_values.insert(value);
         Ok(())
     }
 }
 
 impl Index {
     /// Create an index from bytes.
     /// Calculate the start of each entry when is_inline is true.
     pub fn new(
         bytes: Box<dyn Deref<Target = [u8]> + Send + Sync>,
         default_header: IndexHeader,
     ) -> Result<Self, HgError> {
         let header =
             IndexHeader::parse(bytes.as_ref())?.unwrap_or(default_header);
 
         if header.format_version() != IndexHeader::REVLOGV1 {
             // A proper new version should have had a repo/store
             // requirement.
             return Err(HgError::corrupted("unsupported revlog version"));
         }
 
         // This is only correct because we know version is REVLOGV1.
         // In v2 we always use generaldelta, while in v0 we never use
         // generaldelta. Similar for [is_inline] (it's only used in v1).
         let uses_generaldelta = header.format_flags().uses_generaldelta();
 
         if header.format_flags().is_inline() {
             let mut offset: usize = 0;
             let mut offsets = Vec::new();
 
             while offset + INDEX_ENTRY_SIZE <= bytes.len() {
                 offsets.push(offset);
                 let end = offset + INDEX_ENTRY_SIZE;
                 let entry = IndexEntry {
                     bytes: &bytes[offset..end],
                     offset_override: None,
                 };
 
                 offset += INDEX_ENTRY_SIZE + entry.compressed_len() as usize;
             }
 
             if offset == bytes.len() {
                 Ok(Self {
                     bytes: IndexData::new(bytes),
                     offsets: RwLock::new(Some(offsets)),
                     uses_generaldelta,
                     is_inline: true,
                     head_revs: RwLock::new((vec![], HashSet::new())),
                 })
             } else {
                 Err(HgError::corrupted("unexpected inline revlog length"))
             }
         } else {
             Ok(Self {
                 bytes: IndexData::new(bytes),
                 offsets: RwLock::new(None),
                 uses_generaldelta,
                 is_inline: false,
                 head_revs: RwLock::new((vec![], HashSet::new())),
             })
         }
     }
 
     pub fn uses_generaldelta(&self) -> bool {
         self.uses_generaldelta
     }
 
     /// Value of the inline flag.
     pub fn is_inline(&self) -> bool {
         self.is_inline
     }
 
     /// Return a slice of bytes if `revlog` is inline. Panic if not.
     pub fn data(&self, start: usize, end: usize) -> &[u8] {
         if !self.is_inline() {
             panic!("tried to access data in the index of a revlog that is not inline");
         }
         &self.bytes[start..end]
     }
 
     /// Return number of entries of the revlog index.
     pub fn len(&self) -> usize {
         if let Some(offsets) = &*self.get_offsets() {
             offsets.len()
         } else {
             self.bytes.len() / INDEX_ENTRY_SIZE
         }
     }
 
     pub fn get_offsets(&self) -> RwLockReadGuard<Option<Vec<usize>>> {
         if self.is_inline() {
             {
                 // Wrap in a block to drop the read guard
                 // TODO perf?
                 let mut offsets = self.offsets.write().unwrap();
                 if offsets.is_none() {
                     offsets.replace(inline_scan(&self.bytes.bytes).1);
                 }
             }
         }
         self.offsets.read().unwrap()
     }
 
     pub fn get_offsets_mut(&mut self) -> RwLockWriteGuard<Option<Vec<usize>>> {
         let mut offsets = self.offsets.write().unwrap();
         if self.is_inline() && offsets.is_none() {
             offsets.replace(inline_scan(&self.bytes.bytes).1);
         }
         offsets
     }
 
     /// Returns `true` if the `Index` has zero `entries`.
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
 
     /// Return the index entry corresponding to the given revision or `None`
     /// for [`NULL_REVISION`]
     ///
     /// The specified revision being of the checked type, it always exists
     /// if it was validated by this index.
     pub fn get_entry(&self, rev: Revision) -> Option<IndexEntry> {
         if rev == NULL_REVISION {
             return None;
         }
         Some(if let Some(offsets) = &*self.get_offsets() {
             self.get_entry_inline(rev, offsets.as_ref())
         } else {
             self.get_entry_separated(rev)
         })
     }
 
     /// Return the binary content of the index entry for the given revision
     ///
     /// See [get_entry()](`Self::get_entry()`) for cases when `None` is
     /// returned.
     pub fn entry_binary(&self, rev: Revision) -> Option<&[u8]> {
         self.get_entry(rev).map(|e| {
             let bytes = e.as_bytes();
             if rev.0 == 0 {
                 &bytes[4..]
             } else {
                 bytes
             }
         })
     }
 
     pub fn entry_as_params(
         &self,
         rev: UncheckedRevision,
     ) -> Option<RevisionDataParams> {
         let rev = self.check_revision(rev)?;
         self.get_entry(rev).map(|e| RevisionDataParams {
             flags: e.flags(),
             data_offset: if rev.0 == 0 && !self.bytes.is_new() {
                 e.flags() as u64
             } else {
                 e.raw_offset()
             },
             data_compressed_length: e
                 .compressed_len()
                 .try_into()
                 .unwrap_or_else(|_| {
                     // Python's `unionrepo` sets the compressed length to be
                     // `-1` (or `u32::MAX` if transmuted to `u32`) because it
                     // cannot know the correct compressed length of a given
                     // revision. I'm not sure if this is true, but having this
                     // edge case won't hurt other use cases, let's handle it.
                     assert_eq!(e.compressed_len(), u32::MAX);
                     NULL_REVISION.0
                 }),
             data_uncompressed_length: e.uncompressed_len(),
             data_delta_base: e.base_revision_or_base_of_delta_chain().0,
             link_rev: e.link_revision().0,
             parent_rev_1: e.p1().0,
             parent_rev_2: e.p2().0,
             node_id: e.hash().as_bytes().try_into().unwrap(),
             ..Default::default()
         })
     }
 
     fn get_entry_inline(
         &self,
         rev: Revision,
         offsets: &[usize],
     ) -> IndexEntry {
         let start = offsets[rev.0 as usize];
         let end = start + INDEX_ENTRY_SIZE;
         let bytes = &self.bytes[start..end];
 
         // See IndexEntry for an explanation of this override.
         let offset_override = Some(end);
 
         IndexEntry {
             bytes,
             offset_override,
         }
     }
 
     fn get_entry_separated(&self, rev: Revision) -> IndexEntry {
         let start = rev.0 as usize * INDEX_ENTRY_SIZE;
         let end = start + INDEX_ENTRY_SIZE;
         let bytes = &self.bytes[start..end];
 
         // Override the offset of the first revision as its bytes are used
         // for the index's metadata (saving space because it is always 0)
         let offset_override = if rev == Revision(0) { Some(0) } else { None };
 
         IndexEntry {
             bytes,
             offset_override,
         }
     }
 
     fn null_entry(&self) -> IndexEntry {
         IndexEntry {
             bytes: &[0; INDEX_ENTRY_SIZE],
             offset_override: Some(0),
         }
     }
 
     /// Return the head revisions of this index
     pub fn head_revs(&self) -> Result<Vec<Revision>, GraphError> {
-        self.head_revs_filtered(&HashSet::new())
+        self.head_revs_filtered(&HashSet::new(), false)
+            .map(|h| h.unwrap())
+    }
+
+    /// Python-specific shortcut to save on PyList creation
+    pub fn head_revs_shortcut(
+        &self,
+    ) -> Result<Option<Vec<Revision>>, GraphError> {
+        self.head_revs_filtered(&HashSet::new(), true)
     }
 
     /// Return the head revisions of this index
     pub fn head_revs_filtered(
         &self,
         filtered_revs: &HashSet<Revision>,
-    ) -> Result<Vec<Revision>, GraphError> {
+        py_shortcut: bool,
+    ) -> Result<Option<Vec<Revision>>, GraphError> {
         {
             let guard = self
                 .head_revs
                 .read()
                 .expect("RwLock on Index.head_revs should not be poisoned");
             let self_head_revs = &guard.0;
             let self_filtered_revs = &guard.1;
             if !self_head_revs.is_empty()
                 && filtered_revs == self_filtered_revs
             {
-                return Ok(self_head_revs.to_owned());
+                if py_shortcut {
+                    // Don't copy the revs since we've already cached them
+                    // on the Python side.
+                    return Ok(None);
+                } else {
+                    return Ok(Some(self_head_revs.to_owned()));
+                }
             }
         }
 
         let as_vec = if self.is_empty() {
             vec![NULL_REVISION]
         } else {
             let mut not_heads = bitvec![0; self.len()];
             dagops::retain_heads_fast(
                 self,
                 not_heads.as_mut_bitslice(),
                 filtered_revs,
             )?;
             not_heads
                 .into_iter()
                 .enumerate()
                 .filter_map(|(idx, is_not_head)| {
                     if is_not_head {
                         None
                     } else {
                         Some(Revision(idx as BaseRevision))
                     }
                 })
                 .collect()
         };
         *self
             .head_revs
             .write()
             .expect("RwLock on Index.head_revs should not be poisoned") =
             (as_vec.to_owned(), filtered_revs.to_owned());
-        Ok(as_vec)
+        Ok(Some(as_vec))
     }
 
     /// Obtain the delta chain for a revision.
     ///
     /// `stop_rev` specifies a revision to stop at. If not specified, we
     /// stop at the base of the chain.
     ///
     /// Returns a 2-tuple of (chain, stopped) where `chain` is a vec of
     /// revs in ascending order and `stopped` is a bool indicating whether
     /// `stoprev` was hit.
     pub fn delta_chain(
         &self,
         rev: Revision,
         stop_rev: Option<Revision>,
         using_general_delta: Option<bool>,
     ) -> Result<(Vec<Revision>, bool), HgError> {
         let mut current_rev = rev;
         let mut entry = self.get_entry(rev).unwrap();
         let mut chain = vec![];
         let using_general_delta =
             using_general_delta.unwrap_or_else(|| self.uses_generaldelta());
         while current_rev.0 != entry.base_revision_or_base_of_delta_chain().0
             && stop_rev.map(|r| r != current_rev).unwrap_or(true)
         {
             chain.push(current_rev);
             let new_rev = if using_general_delta {
                 entry.base_revision_or_base_of_delta_chain()
             } else {
                 UncheckedRevision(current_rev.0 - 1)
             };
             current_rev = self.check_revision(new_rev).ok_or_else(|| {
                 HgError::corrupted(format!("Revision {new_rev} out of range"))
             })?;
             if current_rev.0 == NULL_REVISION.0 {
                 break;
             }
             entry = self.get_entry(current_rev).unwrap()
         }
 
         let stopped = if stop_rev.map(|r| current_rev == r).unwrap_or(false) {
             true
         } else {
             chain.push(current_rev);
             false
         };
         chain.reverse();
         Ok((chain, stopped))
     }
 
     pub fn find_snapshots(
         &self,
         start_rev: UncheckedRevision,
         end_rev: UncheckedRevision,
         cache: &mut impl SnapshotsCache,
     ) -> Result<(), RevlogError> {
         let mut start_rev = start_rev.0;
         let mut end_rev = end_rev.0;
         end_rev += 1;
         let len = self.len().try_into().unwrap();
         if end_rev > len {
             end_rev = len;
         }
         if start_rev < 0 {
             start_rev = 0;
         }
         for rev in start_rev..end_rev {
             if !self.is_snapshot_unchecked(Revision(rev))? {
                 continue;
             }
             let mut base = self
                 .get_entry(Revision(rev))
                 .unwrap()
                 .base_revision_or_base_of_delta_chain();
             if base.0 == rev {
                 base = NULL_REVISION.into();
             }
             cache.insert_for(base.0, rev)?;
         }
         Ok(())
     }
 
     fn clear_head_revs(&self) {
         self.head_revs
             .write()
             .expect("RwLock on Index.head_revs should not be poisoined")
             .0
             .clear()
     }
 
     /// TODO move this to the trait probably, along with other things
     pub fn append(
         &mut self,
         revision_data: RevisionDataParams,
     ) -> Result<(), RevlogError> {
         revision_data.validate()?;
         let new_offset = self.bytes.len();
         if let Some(offsets) = &mut *self.get_offsets_mut() {
             offsets.push(new_offset)
         }
         self.bytes.added.extend(revision_data.into_v1().as_bytes());
         self.clear_head_revs();
         Ok(())
     }
 
     pub fn pack_header(&self, header: i32) -> [u8; 4] {
         header.to_be_bytes()
     }
 
     pub fn remove(&mut self, rev: Revision) -> Result<(), RevlogError> {
         let offsets = self.get_offsets().clone();
         self.bytes.remove(rev, offsets.as_deref())?;
         if let Some(offsets) = &mut *self.get_offsets_mut() {
             offsets.truncate(rev.0 as usize)
         }
         self.clear_head_revs();
         Ok(())
     }
 
     pub fn clear_caches(&self) {
         // We need to get the 'inline' value from Python at init and use this
         // instead of offsets to determine whether we're inline since we might
         // clear caches. This implies re-populating the offsets on-demand.
         *self
             .offsets
             .write()
             .expect("RwLock on Index.offsets should not be poisoed") = None;
         self.clear_head_revs();
     }
 
     /// Unchecked version of `is_snapshot`.
     /// Assumes the caller checked that `rev` is within a valid revision range.
     pub fn is_snapshot_unchecked(
         &self,
         mut rev: Revision,
     ) -> Result<bool, RevlogError> {
         while rev.0 >= 0 {
             let entry = self.get_entry(rev).unwrap();
             let mut base = entry.base_revision_or_base_of_delta_chain().0;
             if base == rev.0 {
                 base = NULL_REVISION.0;
             }
             if base == NULL_REVISION.0 {
                 return Ok(true);
             }
             let [mut p1, mut p2] = self
                 .parents(rev)
                 .map_err(|_| RevlogError::InvalidRevision)?;
             while let Some(p1_entry) = self.get_entry(p1) {
                 if p1_entry.compressed_len() != 0 || p1.0 == 0 {
                     break;
                 }
                 let parent_base =
                     p1_entry.base_revision_or_base_of_delta_chain();
                 if parent_base.0 == p1.0 {
                     break;
                 }
                 p1 = self
                     .check_revision(parent_base)
                     .ok_or(RevlogError::InvalidRevision)?;
             }
             while let Some(p2_entry) = self.get_entry(p2) {
                 if p2_entry.compressed_len() != 0 || p2.0 == 0 {
                     break;
                 }
                 let parent_base =
                     p2_entry.base_revision_or_base_of_delta_chain();
                 if parent_base.0 == p2.0 {
                     break;
                 }
                 p2 = self
                     .check_revision(parent_base)
                     .ok_or(RevlogError::InvalidRevision)?;
             }
             if base == p1.0 || base == p2.0 {
                 return Ok(false);
             }
             rev = self
                 .check_revision(base.into())
                 .ok_or(RevlogError::InvalidRevision)?;
         }
         Ok(rev == NULL_REVISION)
     }
 
     /// Return whether the given revision is a snapshot. Returns an error if
     /// `rev` is not within a valid revision range.
     pub fn is_snapshot(
         &self,
         rev: UncheckedRevision,
     ) -> Result<bool, RevlogError> {
         let rev = self
             .check_revision(rev)
             .ok_or_else(|| RevlogError::corrupted("test"))?;
         self.is_snapshot_unchecked(rev)
     }
 
     /// Slice revs to reduce the amount of unrelated data to be read from disk.
     ///
     /// The index is sliced into groups that should be read in one time.
     ///
     /// The initial chunk is sliced until the overall density
     /// (payload/chunks-span ratio) is above `target_density`.
     /// No gap smaller than `min_gap_size` is skipped.
     pub fn slice_chunk_to_density(
         &self,
         revs: &[Revision],
         target_density: f64,
         min_gap_size: usize,
     ) -> Vec<Vec<Revision>> {
         if revs.is_empty() {
             return vec![];
         }
         if revs.len() == 1 {
             return vec![revs.to_owned()];
         }
         let delta_chain_span = self.segment_span(revs);
         if delta_chain_span < min_gap_size {
             return vec![revs.to_owned()];
         }
         let entries: Vec<_> = revs
             .iter()
             .map(|r| {
                 (*r, self.get_entry(*r).unwrap_or_else(|| self.null_entry()))
             })
             .collect();
 
         let mut read_data = delta_chain_span;
         let chain_payload: u32 =
             entries.iter().map(|(_r, e)| e.compressed_len()).sum();
         let mut density = if delta_chain_span > 0 {
             chain_payload as f64 / delta_chain_span as f64
         } else {
             1.0
         };
 
         if density >= target_density {
             return vec![revs.to_owned()];
         }
 
         // Store the gaps in a heap to have them sorted by decreasing size
         let mut gaps = Vec::new();
         let mut previous_end = None;
 
         for (i, (_rev, entry)) in entries.iter().enumerate() {
             let start = entry.c_start() as usize;
             let length = entry.compressed_len();
 
             // Skip empty revisions to form larger holes
             if length == 0 {
                 continue;
             }
 
             if let Some(end) = previous_end {
                 let gap_size = start - end;
                 // Only consider holes that are large enough
                 if gap_size > min_gap_size {
                     gaps.push((gap_size, i));
                 }
             }
             previous_end = Some(start + length as usize);
         }
         if gaps.is_empty() {
             return vec![revs.to_owned()];
         }
         // sort the gaps to pop them from largest to small
         gaps.sort_unstable();
 
         // Collect the indices of the largest holes until
         // the density is acceptable
         let mut selected = vec![];
         while let Some((gap_size, gap_id)) = gaps.pop() {
             if density >= target_density {
                 break;
             }
             selected.push(gap_id);
 
             // The gap sizes are stored as negatives to be sorted decreasingly
             // by the heap
             read_data -= gap_size;
             density = if read_data > 0 {
                 chain_payload as f64 / read_data as f64
             } else {
                 1.0
             };
             if density >= target_density {
                 break;
             }
         }
         selected.sort_unstable();
         selected.push(revs.len());
 
         // Cut the revs at collected indices
         let mut previous_idx = 0;
         let mut chunks = vec![];
         for idx in selected {
             let chunk = self.trim_chunk(&entries, previous_idx, idx);
             if !chunk.is_empty() {
                 chunks.push(chunk.iter().map(|(rev, _entry)| *rev).collect());
             }
             previous_idx = idx;
         }
         let chunk = self.trim_chunk(&entries, previous_idx, entries.len());
         if !chunk.is_empty() {
             chunks.push(chunk.iter().map(|(rev, _entry)| *rev).collect());
         }
 
         chunks
     }
 
     /// Get the byte span of a segment of sorted revisions.
     ///
     /// Occurrences of [`NULL_REVISION`] are ignored at the beginning of
     /// the `revs` segment.
     ///
     /// panics:
     ///  - if `revs` is empty or only made of `NULL_REVISION`
     ///  - if cannot retrieve entry for the last or first not null element of
     ///    `revs`.
     fn segment_span(&self, revs: &[Revision]) -> usize {
         if revs.is_empty() {
             return 0;
         }
         let last_entry = &self.get_entry(revs[revs.len() - 1]).unwrap();
         let end = last_entry.c_start() + last_entry.compressed_len() as u64;
         let first_rev = revs.iter().find(|r| r.0 != NULL_REVISION.0).unwrap();
         let start = if (*first_rev).0 == 0 {
             0
         } else {
             self.get_entry(*first_rev).unwrap().c_start()
         };
         (end - start) as usize
     }
 
     /// Returns `&revs[startidx..endidx]` without empty trailing revs
     fn trim_chunk<'a>(
         &'a self,
         revs: &'a [(Revision, IndexEntry)],
         start: usize,
         mut end: usize,
     ) -> &'a [(Revision, IndexEntry)] {
         // Trim empty revs at the end, except the very first rev of a chain
         let last_rev = revs[end - 1].0;
         if last_rev.0 < self.len() as BaseRevision {
             while end > 1
                 && end > start
                 && revs[end - 1].1.compressed_len() == 0
             {
                 end -= 1
             }
         }
         &revs[start..end]
     }
 
     /// Computes the set of revisions for each non-public phase from `roots`,
     /// which are the last known roots for each non-public phase.
     pub fn compute_phases_map_sets(
         &self,
         roots: HashMap<Phase, Vec<Revision>>,
     ) -> Result<(usize, RootsPerPhase), GraphError> {
         let mut phases = HashMap::new();
         let mut min_phase_rev = NULL_REVISION;
 
         for phase in Phase::non_public_phases() {
             if let Some(phase_roots) = roots.get(phase) {
                 let min_rev =
                     self.add_roots_get_min(phase_roots, &mut phases, *phase);
                 if min_rev != NULL_REVISION
                     && (min_phase_rev == NULL_REVISION
                         || min_rev < min_phase_rev)
                 {
                     min_phase_rev = min_rev;
                 }
             } else {
                 continue;
             };
         }
         let mut phase_sets: RootsPerPhase = Default::default();
 
         if min_phase_rev == NULL_REVISION {
             min_phase_rev = Revision(self.len() as BaseRevision);
         }
 
         for rev in min_phase_rev.0..self.len() as BaseRevision {
             let rev = Revision(rev);
             let [p1, p2] = self.parents(rev)?;
 
             const DEFAULT_PHASE: &Phase = &Phase::Public;
             if p1.0 >= 0
                 && phases.get(&p1).unwrap_or(DEFAULT_PHASE)
                     > phases.get(&rev).unwrap_or(DEFAULT_PHASE)
             {
                 phases.insert(rev, phases[&p1]);
             }
             if p2.0 >= 0
                 && phases.get(&p2).unwrap_or(DEFAULT_PHASE)
                     > phases.get(&rev).unwrap_or(DEFAULT_PHASE)
             {
                 phases.insert(rev, phases[&p2]);
             }
             let set = match phases.get(&rev).unwrap_or(DEFAULT_PHASE) {
                 Phase::Public => continue,
                 phase => &mut phase_sets[*phase as usize - 1],
             };
             set.insert(rev);
         }
 
         Ok((self.len(), phase_sets))
     }
 
     fn add_roots_get_min(
         &self,
         phase_roots: &[Revision],
         phases: &mut HashMap<Revision, Phase>,
         phase: Phase,
     ) -> Revision {
         let mut min_rev = NULL_REVISION;
 
         for root in phase_roots {
             phases.insert(*root, phase);
             if min_rev == NULL_REVISION || min_rev > *root {
                 min_rev = *root;
             }
         }
         min_rev
     }
 
     /// Return `(heads(::(<roots> and <roots>::<heads>)))`
     /// If `include_path` is `true`, return `(<roots>::<heads>)`."""
     ///
     /// `min_root` and `roots` are unchecked since they are just used as
     /// a bound or for comparison and don't need to represent a valid revision.
     /// In practice, the only invalid revision passed is the working directory
     /// revision ([`i32::MAX`]).
     pub fn reachable_roots(
         &self,
         min_root: UncheckedRevision,
         mut heads: Vec<Revision>,
         roots: HashSet<UncheckedRevision>,
         include_path: bool,
     ) -> Result<HashSet<Revision>, GraphError> {
         if roots.is_empty() {
             return Ok(HashSet::new());
         }
         let mut reachable = HashSet::new();
         let mut seen = HashMap::new();
 
         while let Some(rev) = heads.pop() {
             if roots.contains(&rev.into()) {
                 reachable.insert(rev);
                 if !include_path {
                     continue;
                 }
             }
             let parents = self.parents(rev)?;
             seen.insert(rev, parents);
             for parent in parents {
                 if parent.0 >= min_root.0 && !seen.contains_key(&parent) {
                     heads.push(parent);
                 }
             }
         }
         if !include_path {
             return Ok(reachable);
         }
         let mut revs: Vec<_> = seen.keys().collect();
         revs.sort_unstable();
         for rev in revs {
             for parent in seen[rev] {
                 if reachable.contains(&parent) {
                     reachable.insert(*rev);
                 }
             }
         }
         Ok(reachable)
     }
 
     /// Given a (possibly overlapping) set of revs, return all the
     /// common ancestors heads: `heads(::args[0] and ::a[1] and ...)`
     pub fn common_ancestor_heads(
         &self,
         revisions: &[Revision],
     ) -> Result<Vec<Revision>, GraphError> {
         // given that revisions is expected to be small, we find this shortcut
         // potentially acceptable, especially given that `hg-cpython` could
         // very much bypass this, constructing a vector of unique values from
         // the onset.
         let as_set: HashSet<Revision> = revisions.iter().copied().collect();
         // Besides deduplicating, the C version also implements the shortcut
         // for `NULL_REVISION`:
         if as_set.contains(&NULL_REVISION) {
             return Ok(vec![]);
         }
 
         let revisions: Vec<Revision> = as_set.into_iter().collect();
 
         if revisions.len() < 8 {
             self.find_gca_candidates::<u8>(&revisions)
         } else if revisions.len() < 64 {
             self.find_gca_candidates::<u64>(&revisions)
         } else {
             self.find_gca_candidates::<NonStaticPoisonableBitSet>(&revisions)
         }
     }
 
     pub fn ancestors(
         &self,
         revisions: &[Revision],
     ) -> Result<Vec<Revision>, GraphError> {
         self.find_deepest_revs(&self.common_ancestor_heads(revisions)?)
     }
 
     /// Given a disjoint set of revs, return all candidates for the
     /// greatest common ancestor. In revset notation, this is the set
     /// `heads(::a and ::b and ...)`
     fn find_gca_candidates<BS: PoisonableBitSet + Clone>(
         &self,
         revs: &[Revision],
     ) -> Result<Vec<Revision>, GraphError> {
         if revs.is_empty() {
             return Ok(vec![]);
         }
         let revcount = revs.len();
         let mut candidates = vec![];
         let max_rev = revs.iter().max().unwrap();
 
         let mut seen = BS::vec_of_empty(revs.len(), (max_rev.0 + 1) as usize);
 
         for (idx, rev) in revs.iter().enumerate() {
             seen[rev.0 as usize].add(idx);
         }
         let mut current_rev = *max_rev;
         // Number of revisions whose inspection in the main loop
         // will give a result or trigger inspection of other revisions
         let mut interesting = revcount;
 
         // The algorithm works on a vector of bit sets, indexed by revision
         // numbers and iterated on reverse order.
         // An entry in this vector is poisoned if and only if the corresponding
         // revision is a common, yet not maximal ancestor.
 
         // The principle of the algorithm is as follows:
         // For a revision `r`, when entering the loop, `seen[r]` is either
         // poisoned or the sub set of `revs` of which `r` is an ancestor.
         // In this sub set is full, then `r` is a solution and its parents
         // have to be poisoned.
         //
         // At each iteration, the bit sets of the parents are updated by
         // union with `seen[r]`.
         // As we walk the index from the end, we are sure we have encountered
         // all children of `r` before `r`, hence we know that `seen[r]` is
         // fully computed.
         //
         // On top of that there are several optimizations that make reading
         // less obvious than the comment above:
         // - The `interesting` counter allows to break early
         // - The loop starts from `max(revs)`
         // - Early return in case it is detected that one of the incoming revs
         //   is a common ancestor of all of them.
         while current_rev.0 >= 0 && interesting > 0 {
             let current_seen = seen[current_rev.0 as usize].clone();
 
             if current_seen.is_empty() {
                 current_rev = Revision(current_rev.0 - 1);
                 continue;
             }
             let mut poison = current_seen.is_poisoned();
             if !poison {
                 interesting -= 1;
                 if current_seen.is_full_range(revcount) {
                     candidates.push(current_rev);
                     poison = true;
 
                     // Being a common ancestor, if `current_rev` is among
                     // the input revisions, it is *the* answer.
                     for rev in revs {
                         if *rev == current_rev {
                             return Ok(candidates);
                         }
                     }
                 }
             }
             for parent in self.parents(current_rev)? {
                 if parent == NULL_REVISION {
                     continue;
                 }
                 let parent_seen = &mut seen[parent.0 as usize];
                 if poison {
                     // this block is logically equivalent to poisoning parent
                     // and counting it as non interesting if it
                     // has been seen before (hence counted then as interesting)
                     if !parent_seen.is_empty() && !parent_seen.is_poisoned() {
                         interesting -= 1;
                     }
                     parent_seen.poison();
                 } else {
                     if parent_seen.is_empty() {
                         interesting += 1;
                     }
                     parent_seen.union(&current_seen);
                 }
             }
 
             current_rev = Revision(current_rev.0 - 1);
         }
 
         Ok(candidates)
     }
 
     /// Given a disjoint set of revs, return the subset with the longest path
     /// to the root.
     fn find_deepest_revs(
         &self,
         revs: &[Revision],
     ) -> Result<Vec<Revision>, GraphError> {
         // TODO replace this all with just comparing rank?
         // Also, the original implementations in C/Python are cryptic, not
         // even sure we actually need this?
         if revs.len() <= 1 {
             return Ok(revs.to_owned());
         }
         let max_rev = revs.iter().max().unwrap().0;
         let mut interesting = HashMap::new();
         let mut seen = vec![0; max_rev as usize + 1];
         let mut depth = vec![0; max_rev as usize + 1];
         let mut mapping = vec![];
         let mut revs = revs.to_owned();
         revs.sort_unstable();
 
         for (idx, rev) in revs.iter().enumerate() {
             depth[rev.0 as usize] = 1;
             let shift = 1 << idx;
             seen[rev.0 as usize] = shift;
             interesting.insert(shift, 1);
             mapping.push((shift, *rev));
         }
 
         let mut current_rev = Revision(max_rev);
         while current_rev.0 >= 0 && interesting.len() > 1 {
             let current_depth = depth[current_rev.0 as usize];
             if current_depth == 0 {
                 current_rev = Revision(current_rev.0 - 1);
                 continue;
             }
 
             let current_seen = seen[current_rev.0 as usize];
             for parent in self.parents(current_rev)? {
                 if parent == NULL_REVISION {
                     continue;
                 }
                 let parent_seen = seen[parent.0 as usize];
                 let parent_depth = depth[parent.0 as usize];
                 if parent_depth <= current_depth {
                     depth[parent.0 as usize] = current_depth + 1;
                     if parent_seen != current_seen {
                         *interesting.get_mut(&current_seen).unwrap() += 1;
                         seen[parent.0 as usize] = current_seen;
                         if parent_seen != 0 {
                             let parent_interesting =
                                 interesting.get_mut(&parent_seen).unwrap();
                             *parent_interesting -= 1;
                             if *parent_interesting == 0 {
                                 interesting.remove(&parent_seen);
                             }
                         }
                     }
                 } else if current_depth == parent_depth - 1 {
                     let either_seen = parent_seen | current_seen;
                     if either_seen == parent_seen {
                         continue;
                     }
                     seen[parent.0 as usize] = either_seen;
                     interesting
                         .entry(either_seen)
                         .and_modify(|v| *v += 1)
                         .or_insert(1);
                     *interesting.get_mut(&parent_seen).unwrap() -= 1;
                     if interesting[&parent_seen] == 0 {
                         interesting.remove(&parent_seen);
                     }
                 }
             }
             *interesting.get_mut(&current_seen).unwrap() -= 1;
             if interesting[&current_seen] == 0 {
                 interesting.remove(&current_seen);
             }
 
             current_rev = Revision(current_rev.0 - 1);
         }
 
         if interesting.len() != 1 {
             return Ok(vec![]);
         }
         let mask = interesting.keys().next().unwrap();
 
         Ok(mapping
             .into_iter()
             .filter_map(|(shift, rev)| {
                 if (mask & shift) != 0 {
                     return Some(rev);
                 }
                 None
             })
             .collect())
     }
 }
 
 /// The kind of functionality needed by find_gca_candidates
 ///
 /// This is a bit mask which can be declared to be "poisoned", which callers
 /// interpret to break out of some loops.
 ///
 /// The maximum capacity of the bit mask is up to the actual implementation
 trait PoisonableBitSet: Sized + PartialEq {
     /// Return a vector of exactly n elements, initialized to be empty.
     ///
     /// Optimization can vastly depend on implementation. Those being `Copy`
     /// and having constant capacity typically can have a very simple
     /// implementation.
     fn vec_of_empty(sets_size: usize, vec_len: usize) -> Vec<Self>;
 
     /// The size of the bit mask in memory
     fn size(&self) -> usize;
 
     /// The number of elements that can be represented in the set.
     ///
     /// Another way to put it is that it is the highest integer `C` such that
     /// the set is guaranteed to always be a subset of the integer range
     /// `[0, C)`
     fn capacity(&self) -> usize;
 
     /// Declare `n` to belong to the set
     fn add(&mut self, n: usize);
 
     /// Declare `n` not to belong to the set
     fn discard(&mut self, n: usize);
 
     /// Replace this bit set by its union with other
     fn union(&mut self, other: &Self);
 
     /// Poison the bit set
     ///
     /// Interpretation up to the caller
     fn poison(&mut self);
 
     /// Is the bit set poisoned?
     ///
     /// Interpretation is up to the caller
     fn is_poisoned(&self) -> bool;
 
     /// Is the bit set empty?
     fn is_empty(&self) -> bool;
 
     /// return `true` if and only if the bit is the full range `[0, n)`
     /// of integers
     fn is_full_range(&self, n: usize) -> bool;
 }
 
 const U64_POISON: u64 = 1 << 63;
 const U8_POISON: u8 = 1 << 7;
 
 impl PoisonableBitSet for u64 {
     fn vec_of_empty(_sets_size: usize, vec_len: usize) -> Vec<Self> {
         vec![0u64; vec_len]
     }
 
     fn size(&self) -> usize {
         8
     }
 
     fn capacity(&self) -> usize {
         63
     }
 
     fn add(&mut self, n: usize) {
         (*self) |= 1u64 << n;
     }
 
     fn discard(&mut self, n: usize) {
         (*self) &= u64::MAX - (1u64 << n);
     }
 
     fn union(&mut self, other: &Self) {
         if *self != *other {
             (*self) |= *other;
         }
     }
 
     fn is_full_range(&self, n: usize) -> bool {
         *self + 1 == (1u64 << n)
     }
 
     fn is_empty(&self) -> bool {
         *self == 0
     }
 
     fn poison(&mut self) {
         *self = U64_POISON;
     }
 
     fn is_poisoned(&self) -> bool {
         // equality comparison would be tempting but would not resist
         // operations after poisoning (even if these should be bogus).
         *self >= U64_POISON
     }
 }
 
 impl PoisonableBitSet for u8 {
     fn vec_of_empty(_sets_size: usize, vec_len: usize) -> Vec<Self> {
         vec![0; vec_len]
     }
 
     fn size(&self) -> usize {
         1
     }
 
     fn capacity(&self) -> usize {
         7
     }
 
     fn add(&mut self, n: usize) {
         (*self) |= 1 << n;
     }
 
     fn discard(&mut self, n: usize) {
         (*self) &= u8::MAX - (1 << n);
     }
 
     fn union(&mut self, other: &Self) {
         if *self != *other {
             (*self) |= *other;
         }
     }
 
     fn is_full_range(&self, n: usize) -> bool {
         *self + 1 == (1 << n)
     }
 
     fn is_empty(&self) -> bool {
         *self == 0
     }
 
     fn poison(&mut self) {
         *self = U8_POISON;
     }
 
     fn is_poisoned(&self) -> bool {
         // equality comparison would be tempting but would not resist
         // operations after poisoning (even if these should be bogus).
         *self >= U8_POISON
     }
 }
 
 /// A poisonable bit set whose capacity is not known at compile time but
 /// is constant after initial construction
 ///
 /// This can be way further optimized if performance assessments (speed
 /// and/or RAM) require it.
 /// As far as RAM is concerned, for large vectors of these, the main problem
 /// would be the repetition of set_size in each item. We would need a trait
 /// to abstract over the idea of a vector of such bit sets to do better.
 #[derive(Clone, PartialEq)]
 struct NonStaticPoisonableBitSet {
     set_size: usize,
     bit_set: Vec<u64>,
 }
 
 /// Number of `u64` needed for a [`NonStaticPoisonableBitSet`] of given size
 fn non_static_poisonable_inner_len(set_size: usize) -> usize {
     1 + (set_size + 1) / 64
 }
 
 impl NonStaticPoisonableBitSet {
     /// The index of the sub-bit set for the given n, and the index inside
     /// the latter
     fn index(&self, n: usize) -> (usize, usize) {
         (n / 64, n % 64)
     }
 }
 
 /// Mock implementation to ensure that the trait makes sense
 impl PoisonableBitSet for NonStaticPoisonableBitSet {
     fn vec_of_empty(set_size: usize, vec_len: usize) -> Vec<Self> {
         let tmpl = Self {
             set_size,
             bit_set: vec![0u64; non_static_poisonable_inner_len(set_size)],
         };
         vec![tmpl; vec_len]
     }
 
     fn size(&self) -> usize {
         8 + self.bit_set.len() * 8
     }
 
     fn capacity(&self) -> usize {
         self.set_size
     }
 
     fn add(&mut self, n: usize) {
         let (sub_bs, bit_pos) = self.index(n);
         self.bit_set[sub_bs] |= 1 << bit_pos
     }
 
     fn discard(&mut self, n: usize) {
         let (sub_bs, bit_pos) = self.index(n);
         self.bit_set[sub_bs] |= u64::MAX - (1 << bit_pos)
     }
 
     fn union(&mut self, other: &Self) {
         assert!(
             self.set_size == other.set_size,
             "Binary operations on bit sets can only be done on same size"
         );
         for i in 0..self.bit_set.len() - 1 {
             self.bit_set[i] |= other.bit_set[i]
         }
     }
 
     fn is_full_range(&self, n: usize) -> bool {
         let (sub_bs, bit_pos) = self.index(n);
         self.bit_set[..sub_bs].iter().all(|bs| *bs == u64::MAX)
             && self.bit_set[sub_bs] == (1 << (bit_pos + 1)) - 1
     }
 
     fn is_empty(&self) -> bool {
         self.bit_set.iter().all(|bs| *bs == 0u64)
     }
 
     fn poison(&mut self) {
         let (sub_bs, bit_pos) = self.index(self.set_size);
         self.bit_set[sub_bs] = 1 << bit_pos;
     }
 
     fn is_poisoned(&self) -> bool {
         let (sub_bs, bit_pos) = self.index(self.set_size);
         self.bit_set[sub_bs] >= 1 << bit_pos
     }
 }
 
 /// Set of roots of all non-public phases
 pub type RootsPerPhase = [HashSet<Revision>; Phase::non_public_phases().len()];
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd, Hash)]
 pub enum Phase {
     Public = 0,
     Draft = 1,
     Secret = 2,
     Archived = 3,
     Internal = 4,
 }
 
 impl TryFrom<usize> for Phase {
     type Error = RevlogError;
 
     fn try_from(value: usize) -> Result<Self, Self::Error> {
         Ok(match value {
             0 => Self::Public,
             1 => Self::Draft,
             2 => Self::Secret,
             32 => Self::Archived,
             96 => Self::Internal,
             v => {
                 return Err(RevlogError::corrupted(format!(
                     "invalid phase value {}",
                     v
                 )))
             }
         })
     }
 }
 
 impl Phase {
     pub const fn all_phases() -> &'static [Self] {
         &[
             Self::Public,
             Self::Draft,
             Self::Secret,
             Self::Archived,
             Self::Internal,
         ]
     }
     pub const fn non_public_phases() -> &'static [Self] {
         &[Self::Draft, Self::Secret, Self::Archived, Self::Internal]
     }
 }
 
 fn inline_scan(bytes: &[u8]) -> (usize, Vec<usize>) {
     let mut offset: usize = 0;
     let mut offsets = Vec::new();
 
     while offset + INDEX_ENTRY_SIZE <= bytes.len() {
         offsets.push(offset);
         let end = offset + INDEX_ENTRY_SIZE;
         let entry = IndexEntry {
             bytes: &bytes[offset..end],
             offset_override: None,
         };
 
         offset += INDEX_ENTRY_SIZE + entry.compressed_len() as usize;
     }
     (offset, offsets)
 }
 
 impl super::RevlogIndex for Index {
     fn len(&self) -> usize {
         self.len()
     }
 
     fn node(&self, rev: Revision) -> Option<&Node> {
         if rev == NULL_REVISION {
             return Some(&NULL_NODE);
         }
         self.get_entry(rev).map(|entry| entry.hash())
     }
 }
 
 #[derive(Debug)]
 pub struct IndexEntry<'a> {
     bytes: &'a [u8],
     /// Allows to override the offset value of the entry.
     ///
     /// For interleaved index and data, the offset stored in the index
     /// corresponds to the separated data offset.
     /// It has to be overridden with the actual offset in the interleaved
     /// index which is just after the index block.
     ///
     /// For separated index and data, the offset stored in the first index
     /// entry is mixed with the index headers.
     /// It has to be overridden with 0.
     offset_override: Option<usize>,
 }
 
 impl<'a> IndexEntry<'a> {
     /// Return the offset of the data.
     pub fn offset(&self) -> usize {
         if let Some(offset_override) = self.offset_override {
             offset_override
         } else {
             let mut bytes = [0; 8];
             bytes[2..8].copy_from_slice(&self.bytes[0..=5]);
             BigEndian::read_u64(&bytes[..]) as usize
         }
     }
     pub fn raw_offset(&self) -> u64 {
         BigEndian::read_u64(&self.bytes[0..8])
     }
 
     /// Same result (except potentially for rev 0) as C `index_get_start()`
     fn c_start(&self) -> u64 {
         self.raw_offset() >> 16
     }
 
     pub fn flags(&self) -> u16 {
         BigEndian::read_u16(&self.bytes[6..=7])
     }
 
     /// Return the compressed length of the data.
     pub fn compressed_len(&self) -> u32 {
         BigEndian::read_u32(&self.bytes[8..=11])
     }
 
     /// Return the uncompressed length of the data.
     pub fn uncompressed_len(&self) -> i32 {
         BigEndian::read_i32(&self.bytes[12..=15])
     }
 
     /// Return the revision upon which the data has been derived.
     pub fn base_revision_or_base_of_delta_chain(&self) -> UncheckedRevision {
         // TODO Maybe return an Option when base_revision == rev?
         //      Requires to add rev to IndexEntry
 
         BigEndian::read_i32(&self.bytes[16..]).into()
     }
 
     pub fn link_revision(&self) -> UncheckedRevision {
         BigEndian::read_i32(&self.bytes[20..]).into()
     }
 
     pub fn p1(&self) -> UncheckedRevision {
         BigEndian::read_i32(&self.bytes[24..]).into()
     }
 
     pub fn p2(&self) -> UncheckedRevision {
         BigEndian::read_i32(&self.bytes[28..]).into()
     }
 
     /// Return the hash of revision's full text.
     ///
     /// Currently, SHA-1 is used and only the first 20 bytes of this field
     /// are used.
     pub fn hash(&self) -> &'a Node {
         (&self.bytes[32..52]).try_into().unwrap()
     }
 
     pub fn as_bytes(&self) -> &'a [u8] {
         self.bytes
     }
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
     use crate::node::NULL_NODE;
 
     #[cfg(test)]
     #[derive(Debug, Copy, Clone)]
     pub struct IndexEntryBuilder {
         is_first: bool,
         is_inline: bool,
         is_general_delta: bool,
         version: u16,
         offset: usize,
         compressed_len: usize,
         uncompressed_len: usize,
         base_revision_or_base_of_delta_chain: Revision,
         link_revision: Revision,
         p1: Revision,
         p2: Revision,
         node: Node,
     }
 
     #[cfg(test)]
     impl IndexEntryBuilder {
         #[allow(clippy::new_without_default)]
         pub fn new() -> Self {
             Self {
                 is_first: false,
                 is_inline: false,
                 is_general_delta: true,
                 version: 1,
                 offset: 0,
                 compressed_len: 0,
                 uncompressed_len: 0,
                 base_revision_or_base_of_delta_chain: Revision(0),
                 link_revision: Revision(0),
                 p1: NULL_REVISION,
                 p2: NULL_REVISION,
                 node: NULL_NODE,
             }
         }
 
         pub fn is_first(&mut self, value: bool) -> &mut Self {
             self.is_first = value;
             self
         }
 
         pub fn with_inline(&mut self, value: bool) -> &mut Self {
             self.is_inline = value;
             self
         }
 
         pub fn with_general_delta(&mut self, value: bool) -> &mut Self {
             self.is_general_delta = value;
             self
         }
 
         pub fn with_version(&mut self, value: u16) -> &mut Self {
             self.version = value;
             self
         }
 
         pub fn with_offset(&mut self, value: usize) -> &mut Self {
             self.offset = value;
             self
         }
 
         pub fn with_compressed_len(&mut self, value: usize) -> &mut Self {
             self.compressed_len = value;
             self
         }
 
         pub fn with_uncompressed_len(&mut self, value: usize) -> &mut Self {
             self.uncompressed_len = value;
             self
         }
 
         pub fn with_base_revision_or_base_of_delta_chain(
             &mut self,
             value: Revision,
         ) -> &mut Self {
             self.base_revision_or_base_of_delta_chain = value;
             self
         }
 
         pub fn with_link_revision(&mut self, value: Revision) -> &mut Self {
             self.link_revision = value;
             self
         }
 
         pub fn with_p1(&mut self, value: Revision) -> &mut Self {
             self.p1 = value;
             self
         }
 
         pub fn with_p2(&mut self, value: Revision) -> &mut Self {
             self.p2 = value;
             self
         }
 
         pub fn with_node(&mut self, value: Node) -> &mut Self {
             self.node = value;
             self
         }
 
         pub fn build(&self) -> Vec<u8> {
             let mut bytes = Vec::with_capacity(INDEX_ENTRY_SIZE);
             if self.is_first {
                 bytes.extend(&match (self.is_general_delta, self.is_inline) {
                     (false, false) => [0u8, 0],
                     (false, true) => [0u8, 1],
                     (true, false) => [0u8, 2],
                     (true, true) => [0u8, 3],
                 });
                 bytes.extend(&self.version.to_be_bytes());
                 // Remaining offset bytes.
                 bytes.extend(&[0u8; 2]);
             } else {
                 // Offset stored on 48 bits (6 bytes)
                 bytes.extend(&(self.offset as u64).to_be_bytes()[2..]);
             }
             bytes.extend(&[0u8; 2]); // Revision flags.
             bytes.extend(&(self.compressed_len as u32).to_be_bytes());
             bytes.extend(&(self.uncompressed_len as u32).to_be_bytes());
             bytes.extend(
                 &self.base_revision_or_base_of_delta_chain.0.to_be_bytes(),
             );
             bytes.extend(&self.link_revision.0.to_be_bytes());
             bytes.extend(&self.p1.0.to_be_bytes());
             bytes.extend(&self.p2.0.to_be_bytes());
             bytes.extend(self.node.as_bytes());
             bytes.extend(vec![0u8; 12]);
             bytes
         }
     }
 
     pub fn is_inline(index_bytes: &[u8]) -> bool {
         IndexHeader::parse(index_bytes)
             .expect("too short")
             .unwrap()
             .format_flags()
             .is_inline()
     }
 
     pub fn uses_generaldelta(index_bytes: &[u8]) -> bool {
         IndexHeader::parse(index_bytes)
             .expect("too short")
             .unwrap()
             .format_flags()
             .uses_generaldelta()
     }
 
     pub fn get_version(index_bytes: &[u8]) -> u16 {
         IndexHeader::parse(index_bytes)
             .expect("too short")
             .unwrap()
             .format_version()
     }
 
     #[test]
     fn flags_when_no_inline_flag_test() {
         let bytes = IndexEntryBuilder::new()
             .is_first(true)
             .with_general_delta(false)
             .with_inline(false)
             .build();
 
         assert!(!is_inline(&bytes));
         assert!(!uses_generaldelta(&bytes));
     }
 
     #[test]
     fn flags_when_inline_flag_test() {
         let bytes = IndexEntryBuilder::new()
             .is_first(true)
             .with_general_delta(false)
             .with_inline(true)
             .build();
 
         assert!(is_inline(&bytes));
         assert!(!uses_generaldelta(&bytes));
     }
 
     #[test]
     fn flags_when_inline_and_generaldelta_flags_test() {
         let bytes = IndexEntryBuilder::new()
             .is_first(true)
             .with_general_delta(true)
             .with_inline(true)
             .build();
 
         assert!(is_inline(&bytes));
         assert!(uses_generaldelta(&bytes));
     }
 
     #[test]
     fn test_offset() {
         let bytes = IndexEntryBuilder::new().with_offset(1).build();
         let entry = IndexEntry {
             bytes: &bytes,
             offset_override: None,
         };
 
         assert_eq!(entry.offset(), 1)
     }
 
     #[test]
     fn test_with_overridden_offset() {
         let bytes = IndexEntryBuilder::new().with_offset(1).build();
         let entry = IndexEntry {
             bytes: &bytes,
             offset_override: Some(2),
         };
 
         assert_eq!(entry.offset(), 2)
     }
 
     #[test]
     fn test_compressed_len() {
         let bytes = IndexEntryBuilder::new().with_compressed_len(1).build();
         let entry = IndexEntry {
             bytes: &bytes,
             offset_override: None,
         };
 
         assert_eq!(entry.compressed_len(), 1)
     }
 
     #[test]
     fn test_uncompressed_len() {
         let bytes = IndexEntryBuilder::new().with_uncompressed_len(1).build();
         let entry = IndexEntry {
             bytes: &bytes,
             offset_override: None,
         };
 
         assert_eq!(entry.uncompressed_len(), 1)
     }
 
     #[test]
     fn test_base_revision_or_base_of_delta_chain() {
         let bytes = IndexEntryBuilder::new()
             .with_base_revision_or_base_of_delta_chain(Revision(1))
             .build();
         let entry = IndexEntry {
             bytes: &bytes,
             offset_override: None,
         };
 
         assert_eq!(entry.base_revision_or_base_of_delta_chain(), 1.into())
     }
 
     #[test]
     fn link_revision_test() {
         let bytes = IndexEntryBuilder::new()
             .with_link_revision(Revision(123))
             .build();
 
         let entry = IndexEntry {
             bytes: &bytes,
             offset_override: None,
         };
 
         assert_eq!(entry.link_revision(), 123.into());
     }
 
     #[test]
     fn p1_test() {
         let bytes = IndexEntryBuilder::new().with_p1(Revision(123)).build();
 
         let entry = IndexEntry {
             bytes: &bytes,
             offset_override: None,
         };
 
         assert_eq!(entry.p1(), 123.into());
     }
 
     #[test]
     fn p2_test() {
         let bytes = IndexEntryBuilder::new().with_p2(Revision(123)).build();
 
         let entry = IndexEntry {
             bytes: &bytes,
             offset_override: None,
         };
 
         assert_eq!(entry.p2(), 123.into());
     }
 
     #[test]
     fn node_test() {
         let node = Node::from_hex("0123456789012345678901234567890123456789")
             .unwrap();
         let bytes = IndexEntryBuilder::new().with_node(node).build();
 
         let entry = IndexEntry {
             bytes: &bytes,
             offset_override: None,
         };
 
         assert_eq!(*entry.hash(), node);
     }
 
     #[test]
     fn version_test() {
         let bytes = IndexEntryBuilder::new()
             .is_first(true)
             .with_version(2)
             .build();
 
         assert_eq!(get_version(&bytes), 2)
     }
 }
 
 #[cfg(test)]
 pub use tests::IndexEntryBuilder;

rust/hg-cpython/src/revlog.rs

@@ -1,1126 +1,1157 b''
 // revlog.rs
 //
 // Copyright 2019-2020 Georges Racinet <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 use crate::{
     conversion::{rev_pyiter_collect, rev_pyiter_collect_or_else},
     utils::{node_from_py_bytes, node_from_py_object},
     PyRevision,
 };
 use cpython::{
     buffer::{Element, PyBuffer},
     exc::{IndexError, ValueError},
     ObjectProtocol, PyBool, PyBytes, PyClone, PyDict, PyErr, PyInt, PyList,
     PyModule, PyObject, PyResult, PySet, PyString, PyTuple, Python,
     PythonObject, ToPyObject, UnsafePyLeaked,
 };
 use hg::{
     errors::HgError,
     index::{
         IndexHeader, Phase, RevisionDataParams, SnapshotsCache,
         INDEX_ENTRY_SIZE,
     },
     nodemap::{Block, NodeMapError, NodeTree as CoreNodeTree},
     revlog::{nodemap::NodeMap, Graph, NodePrefix, RevlogError, RevlogIndex},
     BaseRevision, Node, Revision, UncheckedRevision, NULL_REVISION,
 };
 use std::{cell::RefCell, collections::HashMap};
 use vcsgraph::graph::Graph as VCSGraph;
 
 pub struct PySharedIndex {
     /// The underlying hg-core index
     pub(crate) inner: &'static hg::index::Index,
 }
 
 /// Return a Struct implementing the Graph trait
 pub(crate) fn py_rust_index_to_graph(
     py: Python,
     index: PyObject,
 ) -> PyResult<UnsafePyLeaked<PySharedIndex>> {
     let midx = index.extract::<Index>(py)?;
     let leaked = midx.index(py).leak_immutable();
     // Safety: we don't leak the "faked" reference out of the `UnsafePyLeaked`
     Ok(unsafe { leaked.map(py, |idx| PySharedIndex { inner: idx }) })
 }
 
 impl Clone for PySharedIndex {
     fn clone(&self) -> Self {
         Self { inner: self.inner }
     }
 }
 
 impl Graph for PySharedIndex {
     #[inline(always)]
     fn parents(&self, rev: Revision) -> Result<[Revision; 2], hg::GraphError> {
         self.inner.parents(rev)
     }
 }
 
 impl VCSGraph for PySharedIndex {
     #[inline(always)]
     fn parents(
         &self,
         rev: BaseRevision,
     ) -> Result<vcsgraph::graph::Parents, vcsgraph::graph::GraphReadError>
     {
         // FIXME This trait should be reworked to decide between Revision
         // and UncheckedRevision, get better errors names, etc.
         match Graph::parents(self, Revision(rev)) {
             Ok(parents) => {
                 Ok(vcsgraph::graph::Parents([parents[0].0, parents[1].0]))
             }
             Err(hg::GraphError::ParentOutOfRange(rev)) => {
                 Err(vcsgraph::graph::GraphReadError::KeyedInvalidKey(rev.0))
             }
         }
     }
 }
 
 impl RevlogIndex for PySharedIndex {
     fn len(&self) -> usize {
         self.inner.len()
     }
     fn node(&self, rev: Revision) -> Option<&Node> {
         self.inner.node(rev)
     }
 }
 
 py_class!(pub class Index |py| {
     @shared data index: hg::index::Index;
     data nt: RefCell<Option<CoreNodeTree>>;
     data docket: RefCell<Option<PyObject>>;
     // Holds a reference to the mmap'ed persistent nodemap data
     data nodemap_mmap: RefCell<Option<PyBuffer>>;
     // Holds a reference to the mmap'ed persistent index data
     data index_mmap: RefCell<Option<PyBuffer>>;
+    data head_revs_py_list: RefCell<Option<PyList>>;
 
     def __new__(
         _cls,
         data: PyObject,
         default_header: u32,
     ) -> PyResult<Self> {
         Self::new(py, data, default_header)
     }
 
     /// Compatibility layer used for Python consumers needing access to the C index
     ///
     /// Only use case so far is `scmutil.shortesthexnodeidprefix`,
     /// that may need to build a custom `nodetree`, based on a specified revset.
     /// With a Rust implementation of the nodemap, we will be able to get rid of
     /// this, by exposing our own standalone nodemap class,
     /// ready to accept `Index`.
 /*    def get_cindex(&self) -> PyResult<PyObject> {
         Ok(self.cindex(py).borrow().inner().clone_ref(py))
     }
 */
     // Index API involving nodemap, as defined in mercurial/pure/parsers.py
 
     /// Return Revision if found, raises a bare `error.RevlogError`
     /// in case of ambiguity, same as C version does
     def get_rev(&self, node: PyBytes) -> PyResult<Option<PyRevision>> {
         let opt = self.get_nodetree(py)?.borrow();
         let nt = opt.as_ref().unwrap();
         let ridx = &*self.index(py).borrow();
         let node = node_from_py_bytes(py, &node)?;
         let rust_rev =
             nt.find_bin(ridx, node.into()).map_err(|e| nodemap_error(py, e))?;
         Ok(rust_rev.map(Into::into))
 
     }
 
     /// same as `get_rev()` but raises a bare `error.RevlogError` if node
     /// is not found.
     ///
     /// No need to repeat `node` in the exception, `mercurial/revlog.py`
     /// will catch and rewrap with it
     def rev(&self, node: PyBytes) -> PyResult<PyRevision> {
         self.get_rev(py, node)?.ok_or_else(|| revlog_error(py))
     }
 
     /// return True if the node exist in the index
     def has_node(&self, node: PyBytes) -> PyResult<bool> {
         // TODO OPTIM we could avoid a needless conversion here,
         // to do when scaffolding for pure Rust switch is removed,
         // as `get_rev()` currently does the necessary assertions
         self.get_rev(py, node).map(|opt| opt.is_some())
     }
 
     /// find length of shortest hex nodeid of a binary ID
     def shortest(&self, node: PyBytes) -> PyResult<usize> {
         let opt = self.get_nodetree(py)?.borrow();
         let nt = opt.as_ref().unwrap();
         let idx = &*self.index(py).borrow();
         match nt.unique_prefix_len_node(idx, &node_from_py_bytes(py, &node)?)
         {
             Ok(Some(l)) => Ok(l),
             Ok(None) => Err(revlog_error(py)),
             Err(e) => Err(nodemap_error(py, e)),
         }
     }
 
     def partialmatch(&self, node: PyObject) -> PyResult<Option<PyBytes>> {
         let opt = self.get_nodetree(py)?.borrow();
         let nt = opt.as_ref().unwrap();
         let idx = &*self.index(py).borrow();
 
         let node_as_string = if cfg!(feature = "python3-sys") {
             node.cast_as::<PyString>(py)?.to_string(py)?.to_string()
         }
         else {
             let node = node.extract::<PyBytes>(py)?;
             String::from_utf8_lossy(node.data(py)).to_string()
         };
 
         let prefix = NodePrefix::from_hex(&node_as_string)
             .map_err(|_| PyErr::new::<ValueError, _>(
                 py, format!("Invalid node or prefix '{}'", node_as_string))
             )?;
 
         nt.find_bin(idx, prefix)
             // TODO make an inner API returning the node directly
             .map(|opt| opt.map(
                 |rev| PyBytes::new(py, idx.node(rev).unwrap().as_bytes())))
             .map_err(|e| nodemap_error(py, e))
 
     }
 
     /// append an index entry
     def append(&self, tup: PyTuple) -> PyResult<PyObject> {
         if tup.len(py) < 8 {
             // this is better than the panic promised by tup.get_item()
             return Err(
                 PyErr::new::<IndexError, _>(py, "tuple index out of range"))
         }
         let node_bytes = tup.get_item(py, 7).extract(py)?;
         let node = node_from_py_object(py, &node_bytes)?;
 
         let rev = self.len(py)? as BaseRevision;
 
         // This is ok since we will just add the revision to the index
         let rev = Revision(rev);
         self.index(py)
             .borrow_mut()
             .append(py_tuple_to_revision_data_params(py, tup)?)
             .unwrap();
         let idx = &*self.index(py).borrow();
         self.get_nodetree(py)?.borrow_mut().as_mut().unwrap()
             .insert(idx, &node, rev)
             .map_err(|e| nodemap_error(py, e))?;
         Ok(py.None())
     }
 
     def __delitem__(&self, key: PyObject) -> PyResult<()> {
         // __delitem__ is both for `del idx[r]` and `del idx[r1:r2]`
         let start = if let Ok(rev) = key.extract(py) {
             UncheckedRevision(rev)
         } else {
             let start = key.getattr(py, "start")?;
             UncheckedRevision(start.extract(py)?)
         };
         let start = self.index(py)
             .borrow()
             .check_revision(start)
             .ok_or_else(|| {
                 nodemap_error(py, NodeMapError::RevisionNotInIndex(start))
             })?;
         self.index(py).borrow_mut().remove(start).unwrap();
         let mut opt = self.get_nodetree(py)?.borrow_mut();
         let nt = opt.as_mut().unwrap();
         nt.invalidate_all();
         self.fill_nodemap(py, nt)?;
         Ok(())
     }
 
     //
     // Index methods previously reforwarded to C index (tp_methods)
     // Same ordering as in revlog.c
     //
 
     /// return the gca set of the given revs
     def ancestors(&self, *args, **_kw) -> PyResult<PyObject> {
         let rust_res = self.inner_ancestors(py, args)?;
         Ok(rust_res)
     }
 
     /// return the heads of the common ancestors of the given revs
     def commonancestorsheads(&self, *args, **_kw) -> PyResult<PyObject> {
         let rust_res = self.inner_commonancestorsheads(py, args)?;
         Ok(rust_res)
     }
 
     /// Clear the index caches and inner py_class data.
     /// It is Python's responsibility to call `update_nodemap_data` again.
     def clearcaches(&self) -> PyResult<PyObject> {
         self.nt(py).borrow_mut().take();
         self.docket(py).borrow_mut().take();
         self.nodemap_mmap(py).borrow_mut().take();
+        self.head_revs_py_list(py).borrow_mut().take();
         self.index(py).borrow().clear_caches();
         Ok(py.None())
     }
 
     /// return the raw binary string representing a revision
     def entry_binary(&self, *args, **_kw) -> PyResult<PyObject> {
         let rindex = self.index(py).borrow();
         let rev = UncheckedRevision(args.get_item(py, 0).extract(py)?);
         let rust_bytes = rindex.check_revision(rev).and_then(
             |r| rindex.entry_binary(r))
             .ok_or_else(|| rev_not_in_index(py, rev))?;
         let rust_res = PyBytes::new(py, rust_bytes).into_object();
         Ok(rust_res)
     }
 
     /// return a binary packed version of the header
     def pack_header(&self, *args, **_kw) -> PyResult<PyObject> {
         let rindex = self.index(py).borrow();
         let packed = rindex.pack_header(args.get_item(py, 0).extract(py)?);
         let rust_res = PyBytes::new(py, &packed).into_object();
         Ok(rust_res)
     }
 
     /// compute phases
     def computephasesmapsets(&self, *args, **_kw) -> PyResult<PyObject> {
         let py_roots = args.get_item(py, 0).extract::<PyDict>(py)?;
         let rust_res = self.inner_computephasesmapsets(py, py_roots)?;
         Ok(rust_res)
     }
 
     /// reachableroots
     def reachableroots2(&self, *args, **_kw) -> PyResult<PyObject> {
         let rust_res = self.inner_reachableroots2(
             py,
             UncheckedRevision(args.get_item(py, 0).extract(py)?),
             args.get_item(py, 1),
             args.get_item(py, 2),
             args.get_item(py, 3).extract(py)?,
         )?;
         Ok(rust_res)
     }
 
     /// get head revisions
     def headrevs(&self) -> PyResult<PyObject> {
         let rust_res = self.inner_headrevs(py)?;
         Ok(rust_res)
     }
 
     /// get filtered head revisions
     def headrevsfiltered(&self, *args, **_kw) -> PyResult<PyObject> {
         let rust_res = self.inner_headrevsfiltered(py, &args.get_item(py, 0))?;
         Ok(rust_res)
     }
 
     /// True if the object is a snapshot
     def issnapshot(&self, *args, **_kw) -> PyResult<bool> {
         let index = self.index(py).borrow();
         let result = index
             .is_snapshot(UncheckedRevision(args.get_item(py, 0).extract(py)?))
             .map_err(|e| {
                 PyErr::new::<cpython::exc::ValueError, _>(py, e.to_string())
             })?;
         Ok(result)
     }
 
     /// Gather snapshot data in a cache dict
     def findsnapshots(&self, *args, **_kw) -> PyResult<PyObject> {
         let index = self.index(py).borrow();
         let cache: PyDict = args.get_item(py, 0).extract(py)?;
         // this methods operates by setting new values in the cache,
         // hence we will compare results by letting the C implementation
         // operate over a deepcopy of the cache, and finally compare both
         // caches.
         let c_cache = PyDict::new(py);
         for (k, v) in cache.items(py) {
             c_cache.set_item(py, k, PySet::new(py, v)?)?;
         }
 
         let start_rev = UncheckedRevision(args.get_item(py, 1).extract(py)?);
         let end_rev = UncheckedRevision(args.get_item(py, 2).extract(py)?);
         let mut cache_wrapper = PySnapshotsCache{ py, dict: cache };
         index.find_snapshots(
             start_rev,
             end_rev,
             &mut cache_wrapper,
         ).map_err(|_| revlog_error(py))?;
         Ok(py.None())
     }
 
     /// determine revisions with deltas to reconstruct fulltext
     def deltachain(&self, *args, **_kw) -> PyResult<PyObject> {
         let index = self.index(py).borrow();
         let rev = args.get_item(py, 0).extract::<BaseRevision>(py)?.into();
         let stop_rev =
             args.get_item(py, 1).extract::<Option<BaseRevision>>(py)?;
         let rev = index.check_revision(rev).ok_or_else(|| {
             nodemap_error(py, NodeMapError::RevisionNotInIndex(rev))
         })?;
         let stop_rev = if let Some(stop_rev) = stop_rev {
             let stop_rev = UncheckedRevision(stop_rev);
             Some(index.check_revision(stop_rev).ok_or_else(|| {
                 nodemap_error(py, NodeMapError::RevisionNotInIndex(stop_rev))
             })?)
         } else {None};
         let using_general_delta = args.get_item(py, 2)
             .extract::<Option<u32>>(py)?
             .map(|i| i != 0);
         let (chain, stopped) = index.delta_chain(
             rev, stop_rev, using_general_delta
         ).map_err(|e| {
             PyErr::new::<cpython::exc::ValueError, _>(py, e.to_string())
         })?;
 
         let chain: Vec<_> = chain.into_iter().map(|r| r.0).collect();
         Ok(
             PyTuple::new(
                 py,
                 &[
                     chain.into_py_object(py).into_object(),
                     stopped.into_py_object(py).into_object()
                 ]
             ).into_object()
         )
 
     }
 
     /// slice planned chunk read to reach a density threshold
     def slicechunktodensity(&self, *args, **_kw) -> PyResult<PyObject> {
         let rust_res = self.inner_slicechunktodensity(
             py,
             args.get_item(py, 0),
             args.get_item(py, 1).extract(py)?,
             args.get_item(py, 2).extract(py)?
         )?;
         Ok(rust_res)
     }
 
     // index_sequence_methods and index_mapping_methods.
     //
     // Since we call back through the high level Python API,
     // there's no point making a distinction between index_get
     // and index_getitem.
     // gracinet 2023: this above is no longer true for the pure Rust impl
 
     def __len__(&self) -> PyResult<usize> {
         self.len(py)
     }
 
     def __getitem__(&self, key: PyObject) -> PyResult<PyObject> {
         let rust_res = self.inner_getitem(py, key.clone_ref(py))?;
         Ok(rust_res)
     }
 
     def __contains__(&self, item: PyObject) -> PyResult<bool> {
         // ObjectProtocol does not seem to provide contains(), so
         // this is an equivalent implementation of the index_contains()
         // defined in revlog.c
         match item.extract::<i32>(py) {
             Ok(rev) => {
                 Ok(rev >= -1 && rev < self.len(py)? as BaseRevision)
             }
             Err(_) => {
                 let item_bytes: PyBytes = item.extract(py)?;
                 let rust_res = self.has_node(py, item_bytes)?;
                 Ok(rust_res)
             }
         }
     }
 
     def nodemap_data_all(&self) -> PyResult<PyBytes> {
         self.inner_nodemap_data_all(py)
     }
 
     def nodemap_data_incremental(&self) -> PyResult<PyObject> {
         self.inner_nodemap_data_incremental(py)
     }
     def update_nodemap_data(
         &self,
         docket: PyObject,
         nm_data: PyObject
     ) -> PyResult<PyObject> {
         self.inner_update_nodemap_data(py, docket, nm_data)
     }
 
     @property
     def entry_size(&self) -> PyResult<PyInt> {
         let rust_res: PyInt = INDEX_ENTRY_SIZE.to_py_object(py);
         Ok(rust_res)
     }
 
     @property
     def rust_ext_compat(&self) -> PyResult<PyInt> {
         // will be entirely removed when the Rust index yet useful to
         // implement in Rust to detangle things when removing `self.cindex`
         let rust_res: PyInt = 1.to_py_object(py);
         Ok(rust_res)
     }
 
     @property
     def is_rust(&self) -> PyResult<PyBool> {
         Ok(false.to_py_object(py))
     }
 
 });
 
 /// Take a (potentially) mmap'ed buffer, and return the underlying Python
 /// buffer along with the Rust slice into said buffer. We need to keep the
 /// Python buffer around, otherwise we'd get a dangling pointer once the buffer
 /// is freed from Python's side.
 ///
 /// # Safety
 ///
 /// The caller must make sure that the buffer is kept around for at least as
 /// long as the slice.
 #[deny(unsafe_op_in_unsafe_fn)]
 unsafe fn mmap_keeparound(
     py: Python,
     data: PyObject,
 ) -> PyResult<(
     PyBuffer,
     Box<dyn std::ops::Deref<Target = [u8]> + Send + Sync + 'static>,
 )> {
     let buf = PyBuffer::get(py, &data)?;
     let len = buf.item_count();
 
     // Build a slice from the mmap'ed buffer data
     let cbuf = buf.buf_ptr();
     let bytes = if std::mem::size_of::<u8>() == buf.item_size()
         && buf.is_c_contiguous()
         && u8::is_compatible_format(buf.format())
     {
         unsafe { std::slice::from_raw_parts(cbuf as *const u8, len) }
     } else {
         return Err(PyErr::new::<ValueError, _>(
             py,
             "Nodemap data buffer has an invalid memory representation"
                 .to_string(),
         ));
     };
 
     Ok((buf, Box::new(bytes)))
 }
 
 fn py_tuple_to_revision_data_params(
     py: Python,
     tuple: PyTuple,
 ) -> PyResult<RevisionDataParams> {
     if tuple.len(py) < 8 {
         // this is better than the panic promised by tup.get_item()
         return Err(PyErr::new::<IndexError, _>(
             py,
             "tuple index out of range",
         ));
     }
     let offset_or_flags: u64 = tuple.get_item(py, 0).extract(py)?;
     let node_id = tuple
         .get_item(py, 7)
         .extract::<PyBytes>(py)?
         .data(py)
         .try_into()
         .unwrap();
     let flags = (offset_or_flags & 0xFFFF) as u16;
     let data_offset = offset_or_flags >> 16;
     Ok(RevisionDataParams {
         flags,
         data_offset,
         data_compressed_length: tuple.get_item(py, 1).extract(py)?,
         data_uncompressed_length: tuple.get_item(py, 2).extract(py)?,
         data_delta_base: tuple.get_item(py, 3).extract(py)?,
         link_rev: tuple.get_item(py, 4).extract(py)?,
         parent_rev_1: tuple.get_item(py, 5).extract(py)?,
         parent_rev_2: tuple.get_item(py, 6).extract(py)?,
         node_id,
         ..Default::default()
     })
 }
 fn revision_data_params_to_py_tuple(
     py: Python,
     params: RevisionDataParams,
 ) -> PyTuple {
     PyTuple::new(
         py,
         &[
             params.data_offset.into_py_object(py).into_object(),
             params
                 .data_compressed_length
                 .into_py_object(py)
                 .into_object(),
             params
                 .data_uncompressed_length
                 .into_py_object(py)
                 .into_object(),
             params.data_delta_base.into_py_object(py).into_object(),
             params.link_rev.into_py_object(py).into_object(),
             params.parent_rev_1.into_py_object(py).into_object(),
             params.parent_rev_2.into_py_object(py).into_object(),
             PyBytes::new(py, &params.node_id)
                 .into_py_object(py)
                 .into_object(),
             params._sidedata_offset.into_py_object(py).into_object(),
             params
                 ._sidedata_compressed_length
                 .into_py_object(py)
                 .into_object(),
             params
                 .data_compression_mode
                 .into_py_object(py)
                 .into_object(),
             params
                 ._sidedata_compression_mode
                 .into_py_object(py)
                 .into_object(),
             params._rank.into_py_object(py).into_object(),
         ],
     )
 }
 
 struct PySnapshotsCache<'p> {
     py: Python<'p>,
     dict: PyDict,
 }
 
 impl<'p> SnapshotsCache for PySnapshotsCache<'p> {
     fn insert_for(
         &mut self,
         rev: BaseRevision,
         value: BaseRevision,
     ) -> Result<(), RevlogError> {
         let pyvalue = value.into_py_object(self.py).into_object();
         match self.dict.get_item(self.py, rev) {
             Some(obj) => obj
                 .extract::<PySet>(self.py)
                 .and_then(|set| set.add(self.py, pyvalue)),
             None => PySet::new(self.py, vec![pyvalue])
                 .and_then(|set| self.dict.set_item(self.py, rev, set)),
         }
         .map_err(|_| {
             RevlogError::Other(HgError::unsupported(
                 "Error in Python caches handling",
             ))
         })
     }
 }
 
 impl Index {
     fn new(py: Python, data: PyObject, header: u32) -> PyResult<Self> {
         // Safety: we keep the buffer around inside the class as `index_mmap`
         let (buf, bytes) = unsafe { mmap_keeparound(py, data)? };
 
         Self::create_instance(
             py,
             hg::index::Index::new(
                 bytes,
                 IndexHeader::parse(&header.to_be_bytes())
                     .expect("default header is broken")
                     .unwrap(),
             )
             .map_err(|e| {
                 revlog_error_with_msg(py, e.to_string().as_bytes())
             })?,
             RefCell::new(None),
             RefCell::new(None),
             RefCell::new(None),
             RefCell::new(Some(buf)),
+            RefCell::new(None),
         )
     }
 
     fn len(&self, py: Python) -> PyResult<usize> {
         let rust_index_len = self.index(py).borrow().len();
         Ok(rust_index_len)
     }
 
     /// This is scaffolding at this point, but it could also become
     /// a way to start a persistent nodemap or perform a
     /// vacuum / repack operation
     fn fill_nodemap(
         &self,
         py: Python,
         nt: &mut CoreNodeTree,
     ) -> PyResult<PyObject> {
         let index = self.index(py).borrow();
         for r in 0..self.len(py)? {
             let rev = Revision(r as BaseRevision);
             // in this case node() won't ever return None
             nt.insert(&*index, index.node(rev).unwrap(), rev)
                 .map_err(|e| nodemap_error(py, e))?
         }
         Ok(py.None())
     }
 
     fn get_nodetree<'a>(
         &'a self,
         py: Python<'a>,
     ) -> PyResult<&'a RefCell<Option<CoreNodeTree>>> {
         if self.nt(py).borrow().is_none() {
             let readonly = Box::<Vec<_>>::default();
             let mut nt = CoreNodeTree::load_bytes(readonly, 0);
             self.fill_nodemap(py, &mut nt)?;
             self.nt(py).borrow_mut().replace(nt);
         }
         Ok(self.nt(py))
     }
 
     /// Returns the full nodemap bytes to be written as-is to disk
     fn inner_nodemap_data_all(&self, py: Python) -> PyResult<PyBytes> {
         let nodemap = self.get_nodetree(py)?.borrow_mut().take().unwrap();
         let (readonly, bytes) = nodemap.into_readonly_and_added_bytes();
 
         // If there's anything readonly, we need to build the data again from
         // scratch
         let bytes = if readonly.len() > 0 {
             let mut nt = CoreNodeTree::load_bytes(Box::<Vec<_>>::default(), 0);
             self.fill_nodemap(py, &mut nt)?;
 
             let (readonly, bytes) = nt.into_readonly_and_added_bytes();
             assert_eq!(readonly.len(), 0);
 
             bytes
         } else {
             bytes
         };
 
         let bytes = PyBytes::new(py, &bytes);
         Ok(bytes)
     }
 
     /// Returns the last saved docket along with the size of any changed data
     /// (in number of blocks), and said data as bytes.
     fn inner_nodemap_data_incremental(
         &self,
         py: Python,
     ) -> PyResult<PyObject> {
         let docket = self.docket(py).borrow();
         let docket = match docket.as_ref() {
             Some(d) => d,
             None => return Ok(py.None()),
         };
 
         let node_tree = self.get_nodetree(py)?.borrow_mut().take().unwrap();
         let masked_blocks = node_tree.masked_readonly_blocks();
         let (_, data) = node_tree.into_readonly_and_added_bytes();
         let changed = masked_blocks * std::mem::size_of::<Block>();
 
         Ok((docket, changed, PyBytes::new(py, &data))
             .to_py_object(py)
             .into_object())
     }
 
     /// Update the nodemap from the new (mmaped) data.
     /// The docket is kept as a reference for later incremental calls.
     fn inner_update_nodemap_data(
         &self,
         py: Python,
         docket: PyObject,
         nm_data: PyObject,
     ) -> PyResult<PyObject> {
         // Safety: we keep the buffer around inside the class as `nodemap_mmap`
         let (buf, bytes) = unsafe { mmap_keeparound(py, nm_data)? };
         let len = buf.item_count();
         self.nodemap_mmap(py).borrow_mut().replace(buf);
 
         let mut nt = CoreNodeTree::load_bytes(bytes, len);
 
         let data_tip = docket
             .getattr(py, "tip_rev")?
             .extract::<BaseRevision>(py)?
             .into();
         self.docket(py).borrow_mut().replace(docket.clone_ref(py));
         let idx = self.index(py).borrow();
         let data_tip = idx.check_revision(data_tip).ok_or_else(|| {
             nodemap_error(py, NodeMapError::RevisionNotInIndex(data_tip))
         })?;
         let current_tip = idx.len();
 
         for r in (data_tip.0 + 1)..current_tip as BaseRevision {
             let rev = Revision(r);
             // in this case node() won't ever return None
             nt.insert(&*idx, idx.node(rev).unwrap(), rev)
                 .map_err(|e| nodemap_error(py, e))?
         }
 
         *self.nt(py).borrow_mut() = Some(nt);
 
         Ok(py.None())
     }
 
     fn inner_getitem(&self, py: Python, key: PyObject) -> PyResult<PyObject> {
         let idx = self.index(py).borrow();
         Ok(match key.extract::<BaseRevision>(py) {
             Ok(key_as_int) => {
                 let entry_params = if key_as_int == NULL_REVISION.0 {
                     RevisionDataParams::default()
                 } else {
                     let rev = UncheckedRevision(key_as_int);
                     match idx.entry_as_params(rev) {
                         Some(e) => e,
                         None => {
                             return Err(PyErr::new::<IndexError, _>(
                                 py,
                                 "revlog index out of range",
                             ));
                         }
                     }
                 };
                 revision_data_params_to_py_tuple(py, entry_params)
                     .into_object()
             }
             _ => self.get_rev(py, key.extract::<PyBytes>(py)?)?.map_or_else(
                 || py.None(),
                 |py_rev| py_rev.into_py_object(py).into_object(),
             ),
         })
     }
 
     fn inner_headrevs(&self, py: Python) -> PyResult<PyObject> {
         let index = &*self.index(py).borrow();
-        let as_vec: Vec<PyObject> = index
-            .head_revs()
-            .map_err(|e| graph_error(py, e))?
-            .iter()
-            .map(|r| PyRevision::from(*r).into_py_object(py).into_object())
-            .collect();
-        Ok(PyList::new(py, &as_vec).into_object())
+        if let Some(new_heads) =
+            index.head_revs_shortcut().map_err(|e| graph_error(py, e))?
+        {
+            self.cache_new_heads_py_list(new_heads, py);
+        }
+
+        Ok(self
+            .head_revs_py_list(py)
+            .borrow()
+            .as_ref()
+            .expect("head revs should be cached")
+            .clone_ref(py)
+            .into_object())
     }
 
     fn inner_headrevsfiltered(
         &self,
         py: Python,
         filtered_revs: &PyObject,
     ) -> PyResult<PyObject> {
         let index = &mut *self.index(py).borrow_mut();
         let filtered_revs = rev_pyiter_collect(py, filtered_revs, index)?;
 
-        let as_vec: Vec<PyObject> = index
-            .head_revs_filtered(&filtered_revs)
+        if let Some(new_heads) = index
+            .head_revs_filtered(&filtered_revs, true)
             .map_err(|e| graph_error(py, e))?
+        {
+            self.cache_new_heads_py_list(new_heads, py);
+        }
+
+        Ok(self
+            .head_revs_py_list(py)
+            .borrow()
+            .as_ref()
+            .expect("head revs should be cached")
+            .clone_ref(py)
+            .into_object())
+    }
+
+    fn cache_new_heads_py_list(
+        &self,
+        new_heads: Vec<Revision>,
+        py: Python<'_>,
+    ) -> PyList {
+        let as_vec: Vec<PyObject> = new_heads
             .iter()
             .map(|r| PyRevision::from(*r).into_py_object(py).into_object())
             .collect();
-        Ok(PyList::new(py, &as_vec).into_object())
+        let new_heads_py_list = PyList::new(py, &as_vec);
+        *self.head_revs_py_list(py).borrow_mut() =
+            Some(new_heads_py_list.clone_ref(py));
+        new_heads_py_list
     }
 
     fn inner_ancestors(
         &self,
         py: Python,
         py_revs: &PyTuple,
     ) -> PyResult<PyObject> {
         let index = &*self.index(py).borrow();
         let revs: Vec<_> = rev_pyiter_collect(py, py_revs.as_object(), index)?;
         let as_vec: Vec<_> = index
             .ancestors(&revs)
             .map_err(|e| graph_error(py, e))?
             .iter()
             .map(|r| PyRevision::from(*r).into_py_object(py).into_object())
             .collect();
         Ok(PyList::new(py, &as_vec).into_object())
     }
 
     fn inner_commonancestorsheads(
         &self,
         py: Python,
         py_revs: &PyTuple,
     ) -> PyResult<PyObject> {
         let index = &*self.index(py).borrow();
         let revs: Vec<_> = rev_pyiter_collect(py, py_revs.as_object(), index)?;
         let as_vec: Vec<_> = index
             .common_ancestor_heads(&revs)
             .map_err(|e| graph_error(py, e))?
             .iter()
             .map(|r| PyRevision::from(*r).into_py_object(py).into_object())
             .collect();
         Ok(PyList::new(py, &as_vec).into_object())
     }
 
     fn inner_computephasesmapsets(
         &self,
         py: Python,
         py_roots: PyDict,
     ) -> PyResult<PyObject> {
         let index = &*self.index(py).borrow();
         let opt = self.get_nodetree(py)?.borrow();
         let nt = opt.as_ref().unwrap();
         let roots: Result<HashMap<Phase, Vec<Revision>>, PyErr> = py_roots
             .items_list(py)
             .iter(py)
             .map(|r| {
                 let phase = r.get_item(py, 0)?;
                 let nodes = r.get_item(py, 1)?;
                 // Transform the nodes from Python to revs here since we
                 // have access to the nodemap
                 let revs: Result<_, _> = nodes
                     .iter(py)?
                     .map(|node| match node?.extract::<PyBytes>(py) {
                         Ok(py_bytes) => {
                             let node = node_from_py_bytes(py, &py_bytes)?;
                             nt.find_bin(index, node.into())
                                 .map_err(|e| nodemap_error(py, e))?
                                 .ok_or_else(|| revlog_error(py))
                         }
                         Err(e) => Err(e),
                     })
                     .collect();
                 let phase = Phase::try_from(phase.extract::<usize>(py)?)
                     .map_err(|_| revlog_error(py));
                 Ok((phase?, revs?))
             })
             .collect();
         let (len, phase_maps) = index
             .compute_phases_map_sets(roots?)
             .map_err(|e| graph_error(py, e))?;
 
         // Ugly hack, but temporary
         const IDX_TO_PHASE_NUM: [usize; 4] = [1, 2, 32, 96];
         let py_phase_maps = PyDict::new(py);
         for (idx, roots) in phase_maps.iter().enumerate() {
             let phase_num = IDX_TO_PHASE_NUM[idx].into_py_object(py);
             // OPTIM too bad we have to collect here. At least, we could
             // reuse the same Vec and allocate it with capacity at
             // max(len(phase_maps)
             let roots_vec: Vec<PyInt> = roots
                 .iter()
                 .map(|r| PyRevision::from(*r).into_py_object(py))
                 .collect();
             py_phase_maps.set_item(
                 py,
                 phase_num,
                 PySet::new(py, roots_vec)?,
             )?;
         }
         Ok(PyTuple::new(
             py,
             &[
                 len.into_py_object(py).into_object(),
                 py_phase_maps.into_object(),
             ],
         )
         .into_object())
     }
 
     fn inner_slicechunktodensity(
         &self,
         py: Python,
         revs: PyObject,
         target_density: f64,
         min_gap_size: usize,
     ) -> PyResult<PyObject> {
         let index = &*self.index(py).borrow();
         let revs: Vec<_> = rev_pyiter_collect(py, &revs, index)?;
         let as_nested_vec =
             index.slice_chunk_to_density(&revs, target_density, min_gap_size);
         let mut res = Vec::with_capacity(as_nested_vec.len());
         let mut py_chunk = Vec::new();
         for chunk in as_nested_vec {
             py_chunk.clear();
             py_chunk.reserve_exact(chunk.len());
             for rev in chunk {
                 py_chunk.push(
                     PyRevision::from(rev).into_py_object(py).into_object(),
                 );
             }
             res.push(PyList::new(py, &py_chunk).into_object());
         }
         // This is just to do the same as C, not sure why it does this
         if res.len() == 1 {
             Ok(PyTuple::new(py, &res).into_object())
         } else {
             Ok(PyList::new(py, &res).into_object())
         }
     }
 
     fn inner_reachableroots2(
         &self,
         py: Python,
         min_root: UncheckedRevision,
         heads: PyObject,
         roots: PyObject,
         include_path: bool,
     ) -> PyResult<PyObject> {
         let index = &*self.index(py).borrow();
         let heads = rev_pyiter_collect_or_else(py, &heads, index, |_rev| {
             PyErr::new::<IndexError, _>(py, "head out of range")
         })?;
         let roots: Result<_, _> = roots
             .iter(py)?
             .map(|r| {
                 r.and_then(|o| match o.extract::<PyRevision>(py) {
                     Ok(r) => Ok(UncheckedRevision(r.0)),
                     Err(e) => Err(e),
                 })
             })
             .collect();
         let as_set = index
             .reachable_roots(min_root, heads, roots?, include_path)
             .map_err(|e| graph_error(py, e))?;
         let as_vec: Vec<PyObject> = as_set
             .iter()
             .map(|r| PyRevision::from(*r).into_py_object(py).into_object())
             .collect();
         Ok(PyList::new(py, &as_vec).into_object())
     }
 }
 
 py_class!(pub class NodeTree |py| {
     data nt: RefCell<CoreNodeTree>;
     data index: RefCell<UnsafePyLeaked<PySharedIndex>>;
 
     def __new__(_cls, index: PyObject) -> PyResult<NodeTree> {
         let index = py_rust_index_to_graph(py, index)?;
         let nt = CoreNodeTree::default();  // in-RAM, fully mutable
         Self::create_instance(py, RefCell::new(nt), RefCell::new(index))
     }
 
     /// Tell whether the NodeTree is still valid
     ///
     /// In case of mutation of the index, the given results are not
     /// guaranteed to be correct, and in fact, the methods borrowing
     /// the inner index would fail because of `PySharedRef` poisoning
     /// (generation-based guard), same as iterating on a `dict` that has
     /// been meanwhile mutated.
     def is_invalidated(&self) -> PyResult<bool> {
         let leaked = self.index(py).borrow();
         // Safety: we don't leak the "faked" reference out of `UnsafePyLeaked`
         let result = unsafe { leaked.try_borrow(py) };
         // two cases for result to be an error:
         // - the index has previously been mutably borrowed
         // - there is currently a mutable borrow
         // in both cases this amounts for previous results related to
         // the index to still be valid.
         Ok(result.is_err())
     }
 
     def insert(&self, rev: PyRevision) -> PyResult<PyObject> {
         let leaked = self.index(py).borrow();
         // Safety: we don't leak the "faked" reference out of `UnsafePyLeaked`
         let index = &*unsafe { leaked.try_borrow(py)? };
 
         let rev = UncheckedRevision(rev.0);
         let rev = index
             .check_revision(rev)
             .ok_or_else(|| rev_not_in_index(py, rev))?;
         if rev == NULL_REVISION {
             return Err(rev_not_in_index(py, rev.into()))
         }
 
         let entry = index.inner.get_entry(rev).unwrap();
         let mut nt = self.nt(py).borrow_mut();
         nt.insert(index, entry.hash(), rev).map_err(|e| nodemap_error(py, e))?;
 
         Ok(py.None())
     }
 
     /// Lookup by node hex prefix in the NodeTree, returning revision number.
     ///
     /// This is not part of the classical NodeTree API, but is good enough
     /// for unit testing, as in `test-rust-revlog.py`.
     def prefix_rev_lookup(
         &self,
         node_prefix: PyBytes
     ) -> PyResult<Option<PyRevision>> {
         let prefix = NodePrefix::from_hex(node_prefix.data(py))
             .map_err(|_| PyErr::new::<ValueError, _>(
                 py,
                 format!("Invalid node or prefix {:?}",
                         node_prefix.as_object()))
             )?;
 
         let nt = self.nt(py).borrow();
         let leaked = self.index(py).borrow();
         // Safety: we don't leak the "faked" reference out of `UnsafePyLeaked`
         let index = &*unsafe { leaked.try_borrow(py)? };
 
         Ok(nt.find_bin(index, prefix)
                .map_err(|e| nodemap_error(py, e))?
                .map(|r| r.into())
         )
     }
 
     def shortest(&self, node: PyBytes) -> PyResult<usize> {
         let nt = self.nt(py).borrow();
         let leaked = self.index(py).borrow();
         // Safety: we don't leak the "faked" reference out of `UnsafePyLeaked`
         let idx = &*unsafe { leaked.try_borrow(py)? };
         match nt.unique_prefix_len_node(idx, &node_from_py_bytes(py, &node)?)
         {
             Ok(Some(l)) => Ok(l),
             Ok(None) => Err(revlog_error(py)),
             Err(e) => Err(nodemap_error(py, e)),
         }
     }
 });
 
 fn revlog_error(py: Python) -> PyErr {
     match py
         .import("mercurial.error")
         .and_then(|m| m.get(py, "RevlogError"))
     {
         Err(e) => e,
         Ok(cls) => PyErr::from_instance(
             py,
             cls.call(py, (py.None(),), None).ok().into_py_object(py),
         ),
     }
 }
 
 fn revlog_error_with_msg(py: Python, msg: &[u8]) -> PyErr {
     match py
         .import("mercurial.error")
         .and_then(|m| m.get(py, "RevlogError"))
     {
         Err(e) => e,
         Ok(cls) => PyErr::from_instance(
             py,
             cls.call(py, (PyBytes::new(py, msg),), None)
                 .ok()
                 .into_py_object(py),
         ),
     }
 }
 
 fn graph_error(py: Python, _err: hg::GraphError) -> PyErr {
     // ParentOutOfRange is currently the only alternative
     // in `hg::GraphError`. The C index always raises this simple ValueError.
     PyErr::new::<ValueError, _>(py, "parent out of range")
 }
 
 fn nodemap_rev_not_in_index(py: Python, rev: UncheckedRevision) -> PyErr {
     PyErr::new::<ValueError, _>(
         py,
         format!(
             "Inconsistency: Revision {} found in nodemap \
              is not in revlog index",
             rev
         ),
     )
 }
 
 fn rev_not_in_index(py: Python, rev: UncheckedRevision) -> PyErr {
     PyErr::new::<ValueError, _>(
         py,
         format!("revlog index out of range: {}", rev),
     )
 }
 
 /// Standard treatment of NodeMapError
 fn nodemap_error(py: Python, err: NodeMapError) -> PyErr {
     match err {
         NodeMapError::MultipleResults => revlog_error(py),
         NodeMapError::RevisionNotInIndex(r) => nodemap_rev_not_in_index(py, r),
     }
 }
 
 /// Create the module, with __package__ given from parent
 pub fn init_module(py: Python, package: &str) -> PyResult<PyModule> {
     let dotted_name = &format!("{}.revlog", package);
     let m = PyModule::new(py, dotted_name)?;
     m.add(py, "__package__", package)?;
     m.add(py, "__doc__", "RevLog - Rust implementations")?;
 
     m.add_class::<Index>(py)?;
     m.add_class::<NodeTree>(py)?;
 
     let sys = PyModule::import(py, "sys")?;
     let sys_modules: PyDict = sys.get(py, "modules")?.extract(py)?;
     sys_modules.set_item(py, dotted_name, &m)?;
 
     Ok(m)
 }