rust: implement the `Graph` trait for all revlogs

This is trivial and makes all the algorithms relying on the trait usable
for more use cases.

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

@@ -1,353 +1,359 b''
 use crate::errors::HgError;
 use crate::revlog::Revision;
 use crate::revlog::{Node, NodePrefix};
 use crate::revlog::{Revlog, RevlogEntry, RevlogError};
 use crate::utils::hg_path::HgPath;
 use crate::vfs::Vfs;
-use crate::UncheckedRevision;
+use crate::{Graph, GraphError, UncheckedRevision};
 use itertools::Itertools;
 use std::ascii::escape_default;
 use std::borrow::Cow;
 use std::fmt::{Debug, Formatter};
 
 /// A specialized `Revlog` to work with changelog data format.
 pub struct Changelog {
     /// The generic `revlog` format.
     pub(crate) revlog: Revlog,
 }
 
 impl Changelog {
     /// Open the `changelog` of a repository given by its root.
     pub fn open(store_vfs: &Vfs, use_nodemap: bool) -> Result<Self, HgError> {
         let revlog =
             Revlog::open(store_vfs, "00changelog.i", None, use_nodemap)?;
         Ok(Self { revlog })
     }
 
     /// Return the `ChangelogRevisionData` for the given node ID.
     pub fn data_for_node(
         &self,
         node: NodePrefix,
     ) -> Result<ChangelogRevisionData, RevlogError> {
         let rev = self.revlog.rev_from_node(node)?;
         self.entry_for_checked_rev(rev)?.data()
     }
 
     /// Return the [`ChangelogEntry`] for the given revision number.
     pub fn entry_for_rev(
         &self,
         rev: UncheckedRevision,
     ) -> Result<ChangelogEntry, RevlogError> {
         let revlog_entry = self.revlog.get_entry(rev)?;
         Ok(ChangelogEntry { revlog_entry })
     }
 
     /// Same as [`Self::entry_for_rev`] for checked revisions.
     fn entry_for_checked_rev(
         &self,
         rev: Revision,
     ) -> Result<ChangelogEntry, RevlogError> {
         let revlog_entry = self.revlog.get_entry_for_checked_rev(rev)?;
         Ok(ChangelogEntry { revlog_entry })
     }
 
     /// Return the [`ChangelogRevisionData`] for the given revision number.
     ///
     /// This is a useful shortcut in case the caller does not need the
     /// generic revlog information (parents, hashes etc). Otherwise
     /// consider taking a [`ChangelogEntry`] with
     /// [entry_for_rev](`Self::entry_for_rev`) and doing everything from there.
     pub fn data_for_rev(
         &self,
         rev: UncheckedRevision,
     ) -> Result<ChangelogRevisionData, RevlogError> {
         self.entry_for_rev(rev)?.data()
     }
 
     pub fn node_from_rev(&self, rev: UncheckedRevision) -> Option<&Node> {
         self.revlog.node_from_rev(rev)
     }
 
     pub fn rev_from_node(
         &self,
         node: NodePrefix,
     ) -> Result<Revision, RevlogError> {
         self.revlog.rev_from_node(node)
     }
 }
 
+impl Graph for Changelog {
+    fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
+        self.revlog.parents(rev)
+    }
+}
+
 /// A specialized `RevlogEntry` for `changelog` data format
 ///
 /// This is a `RevlogEntry` with the added semantics that the associated
 /// data should meet the requirements for `changelog`, materialized by
 /// the fact that `data()` constructs a `ChangelogRevisionData`.
 /// In case that promise would be broken, the `data` method returns an error.
 #[derive(Clone)]
 pub struct ChangelogEntry<'changelog> {
     /// Same data, as a generic `RevlogEntry`.
     pub(crate) revlog_entry: RevlogEntry<'changelog>,
 }
 
 impl<'changelog> ChangelogEntry<'changelog> {
     pub fn data<'a>(
         &'a self,
     ) -> Result<ChangelogRevisionData<'changelog>, RevlogError> {
         let bytes = self.revlog_entry.data()?;
         if bytes.is_empty() {
             Ok(ChangelogRevisionData::null())
         } else {
             Ok(ChangelogRevisionData::new(bytes).map_err(|err| {
                 RevlogError::Other(HgError::CorruptedRepository(format!(
                     "Invalid changelog data for revision {}: {:?}",
                     self.revlog_entry.revision(),
                     err
                 )))
             })?)
         }
     }
 
     /// Obtain a reference to the underlying `RevlogEntry`.
     ///
     /// This allows the caller to access the information that is common
     /// to all revlog entries: revision number, node id, parent revisions etc.
     pub fn as_revlog_entry(&self) -> &RevlogEntry {
         &self.revlog_entry
     }
 
     pub fn p1_entry(&self) -> Result<Option<ChangelogEntry>, RevlogError> {
         Ok(self
             .revlog_entry
             .p1_entry()?
             .map(|revlog_entry| Self { revlog_entry }))
     }
 
     pub fn p2_entry(&self) -> Result<Option<ChangelogEntry>, RevlogError> {
         Ok(self
             .revlog_entry
             .p2_entry()?
             .map(|revlog_entry| Self { revlog_entry }))
     }
 }
 
 /// `Changelog` entry which knows how to interpret the `changelog` data bytes.
 #[derive(PartialEq)]
 pub struct ChangelogRevisionData<'changelog> {
     /// The data bytes of the `changelog` entry.
     bytes: Cow<'changelog, [u8]>,
     /// The end offset for the hex manifest (not including the newline)
     manifest_end: usize,
     /// The end offset for the user+email (not including the newline)
     user_end: usize,
     /// The end offset for the timestamp+timezone+extras (not including the
     /// newline)
     timestamp_end: usize,
     /// The end offset for the file list (not including the newline)
     files_end: usize,
 }
 
 impl<'changelog> ChangelogRevisionData<'changelog> {
     fn new(bytes: Cow<'changelog, [u8]>) -> Result<Self, HgError> {
         let mut line_iter = bytes.split(|b| b == &b'\n');
         let manifest_end = line_iter
             .next()
             .expect("Empty iterator from split()?")
             .len();
         let user_slice = line_iter.next().ok_or_else(|| {
             HgError::corrupted("Changeset data truncated after manifest line")
         })?;
         let user_end = manifest_end + 1 + user_slice.len();
         let timestamp_slice = line_iter.next().ok_or_else(|| {
             HgError::corrupted("Changeset data truncated after user line")
         })?;
         let timestamp_end = user_end + 1 + timestamp_slice.len();
         let mut files_end = timestamp_end + 1;
         loop {
             let line = line_iter.next().ok_or_else(|| {
                 HgError::corrupted("Changeset data truncated in files list")
             })?;
             if line.is_empty() {
                 if files_end == bytes.len() {
                     // The list of files ended with a single newline (there
                     // should be two)
                     return Err(HgError::corrupted(
                         "Changeset data truncated after files list",
                     ));
                 }
                 files_end -= 1;
                 break;
             }
             files_end += line.len() + 1;
         }
 
         Ok(Self {
             bytes,
             manifest_end,
             user_end,
             timestamp_end,
             files_end,
         })
     }
 
     fn null() -> Self {
         Self::new(Cow::Borrowed(
             b"0000000000000000000000000000000000000000\n\n0 0\n\n",
         ))
         .unwrap()
     }
 
     /// Return an iterator over the lines of the entry.
     pub fn lines(&self) -> impl Iterator<Item = &[u8]> {
         self.bytes.split(|b| b == &b'\n')
     }
 
     /// Return the node id of the `manifest` referenced by this `changelog`
     /// entry.
     pub fn manifest_node(&self) -> Result<Node, HgError> {
         let manifest_node_hex = &self.bytes[..self.manifest_end];
         Node::from_hex_for_repo(manifest_node_hex)
     }
 
     /// The full user string (usually a name followed by an email enclosed in
     /// angle brackets)
     pub fn user(&self) -> &[u8] {
         &self.bytes[self.manifest_end + 1..self.user_end]
     }
 
     /// The full timestamp line (timestamp in seconds, offset in seconds, and
     /// possibly extras)
     // TODO: We should expose this in a more useful way
     pub fn timestamp_line(&self) -> &[u8] {
         &self.bytes[self.user_end + 1..self.timestamp_end]
     }
 
     /// The files changed in this revision.
     pub fn files(&self) -> impl Iterator<Item = &HgPath> {
         self.bytes[self.timestamp_end + 1..self.files_end]
             .split(|b| b == &b'\n')
             .map(HgPath::new)
     }
 
     /// The change description.
     pub fn description(&self) -> &[u8] {
         &self.bytes[self.files_end + 2..]
     }
 }
 
 impl Debug for ChangelogRevisionData<'_> {
     fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
         f.debug_struct("ChangelogRevisionData")
             .field("bytes", &debug_bytes(&self.bytes))
             .field("manifest", &debug_bytes(&self.bytes[..self.manifest_end]))
             .field(
                 "user",
                 &debug_bytes(
                     &self.bytes[self.manifest_end + 1..self.user_end],
                 ),
             )
             .field(
                 "timestamp",
                 &debug_bytes(
                     &self.bytes[self.user_end + 1..self.timestamp_end],
                 ),
             )
             .field(
                 "files",
                 &debug_bytes(
                     &self.bytes[self.timestamp_end + 1..self.files_end],
                 ),
             )
             .field(
                 "description",
                 &debug_bytes(&self.bytes[self.files_end + 2..]),
             )
             .finish()
     }
 }
 
 fn debug_bytes(bytes: &[u8]) -> String {
     String::from_utf8_lossy(
         &bytes.iter().flat_map(|b| escape_default(*b)).collect_vec(),
     )
     .to_string()
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
     use crate::vfs::Vfs;
     use crate::NULL_REVISION;
     use pretty_assertions::assert_eq;
 
     #[test]
     fn test_create_changelogrevisiondata_invalid() {
         // Completely empty
         assert!(ChangelogRevisionData::new(Cow::Borrowed(b"abcd")).is_err());
         // No newline after manifest
         assert!(ChangelogRevisionData::new(Cow::Borrowed(b"abcd")).is_err());
         // No newline after user
         assert!(ChangelogRevisionData::new(Cow::Borrowed(b"abcd\n")).is_err());
         // No newline after timestamp
         assert!(
             ChangelogRevisionData::new(Cow::Borrowed(b"abcd\n\n0 0")).is_err()
         );
         // Missing newline after files
         assert!(ChangelogRevisionData::new(Cow::Borrowed(
             b"abcd\n\n0 0\nfile1\nfile2"
         ))
         .is_err(),);
         // Only one newline after files
         assert!(ChangelogRevisionData::new(Cow::Borrowed(
             b"abcd\n\n0 0\nfile1\nfile2\n"
         ))
         .is_err(),);
     }
 
     #[test]
     fn test_create_changelogrevisiondata() {
         let data = ChangelogRevisionData::new(Cow::Borrowed(
             b"0123456789abcdef0123456789abcdef01234567
 Some One <[e-mail]>
 0 0
 file1
 file2
 
 some
 commit
 message",
         ))
         .unwrap();
         assert_eq!(
             data.manifest_node().unwrap(),
             Node::from_hex("0123456789abcdef0123456789abcdef01234567")
                 .unwrap()
         );
         assert_eq!(data.user(), b"Some One <[e-mail]>");
         assert_eq!(data.timestamp_line(), b"0 0");
         assert_eq!(
             data.files().collect_vec(),
             vec![HgPath::new("file1"), HgPath::new("file2")]
         );
         assert_eq!(data.description(), b"some\ncommit\nmessage");
     }
 
     #[test]
     fn test_data_from_rev_null() -> Result<(), RevlogError> {
         // an empty revlog will be enough for this case
         let temp = tempfile::tempdir().unwrap();
         let vfs = Vfs { base: temp.path() };
         std::fs::write(temp.path().join("foo.i"), b"").unwrap();
         let revlog = Revlog::open(&vfs, "foo.i", None, false).unwrap();
 
         let changelog = Changelog { revlog };
         assert_eq!(
             changelog.data_for_rev(NULL_REVISION.into())?,
             ChangelogRevisionData::null()
         );
         // same with the intermediate entry object
         assert_eq!(
             changelog.entry_for_rev(NULL_REVISION.into())?.data()?,
             ChangelogRevisionData::null()
         );
         Ok(())
     }
 }

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

@@ -1,231 +1,239 b''
 use crate::errors::HgError;
 use crate::exit_codes;
 use crate::repo::Repo;
 use crate::revlog::path_encode::path_encode;
 use crate::revlog::NodePrefix;
 use crate::revlog::Revision;
 use crate::revlog::RevlogEntry;
 use crate::revlog::{Revlog, RevlogError};
 use crate::utils::files::get_path_from_bytes;
 use crate::utils::hg_path::HgPath;
 use crate::utils::SliceExt;
+use crate::Graph;
+use crate::GraphError;
 use crate::UncheckedRevision;
 use std::path::PathBuf;
 
 /// A specialized `Revlog` to work with file data logs.
 pub struct Filelog {
     /// The generic `revlog` format.
     revlog: Revlog,
 }
 
+impl Graph for Filelog {
+    fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
+        self.revlog.parents(rev)
+    }
+}
+
 impl Filelog {
     pub fn open_vfs(
         store_vfs: &crate::vfs::Vfs<'_>,
         file_path: &HgPath,
     ) -> Result<Self, HgError> {
         let index_path = store_path(file_path, b".i");
         let data_path = store_path(file_path, b".d");
         let revlog =
             Revlog::open(store_vfs, index_path, Some(&data_path), false)?;
         Ok(Self { revlog })
     }
 
     pub fn open(repo: &Repo, file_path: &HgPath) -> Result<Self, HgError> {
         Self::open_vfs(&repo.store_vfs(), file_path)
     }
 
     /// The given node ID is that of the file as found in a filelog, not of a
     /// changeset.
     pub fn data_for_node(
         &self,
         file_node: impl Into<NodePrefix>,
     ) -> Result<FilelogRevisionData, RevlogError> {
         let file_rev = self.revlog.rev_from_node(file_node.into())?;
         self.data_for_rev(file_rev.into())
     }
 
     /// The given revision is that of the file as found in a filelog, not of a
     /// changeset.
     pub fn data_for_rev(
         &self,
         file_rev: UncheckedRevision,
     ) -> Result<FilelogRevisionData, RevlogError> {
         let data: Vec<u8> = self.revlog.get_rev_data(file_rev)?.into_owned();
         Ok(FilelogRevisionData(data))
     }
 
     /// The given node ID is that of the file as found in a filelog, not of a
     /// changeset.
     pub fn entry_for_node(
         &self,
         file_node: impl Into<NodePrefix>,
     ) -> Result<FilelogEntry, RevlogError> {
         let file_rev = self.revlog.rev_from_node(file_node.into())?;
         self.entry_for_checked_rev(file_rev)
     }
 
     /// The given revision is that of the file as found in a filelog, not of a
     /// changeset.
     pub fn entry_for_rev(
         &self,
         file_rev: UncheckedRevision,
     ) -> Result<FilelogEntry, RevlogError> {
         Ok(FilelogEntry(self.revlog.get_entry(file_rev)?))
     }
 
     fn entry_for_checked_rev(
         &self,
         file_rev: Revision,
     ) -> Result<FilelogEntry, RevlogError> {
         Ok(FilelogEntry(
             self.revlog.get_entry_for_checked_rev(file_rev)?,
         ))
     }
 }
 
 fn store_path(hg_path: &HgPath, suffix: &[u8]) -> PathBuf {
     let encoded_bytes =
         path_encode(&[b"data/", hg_path.as_bytes(), suffix].concat());
     get_path_from_bytes(&encoded_bytes).into()
 }
 
 pub struct FilelogEntry<'a>(RevlogEntry<'a>);
 
 impl FilelogEntry<'_> {
     /// `self.data()` can be expensive, with decompression and delta
     /// resolution.
     ///
     /// *Without* paying this cost, based on revlog index information
     /// including `RevlogEntry::uncompressed_len`:
     ///
     /// * Returns `true` if the length that `self.data().file_data().len()`
     ///   would return is definitely **not equal** to `other_len`.
     /// * Returns `false` if available information is inconclusive.
     pub fn file_data_len_not_equal_to(&self, other_len: u64) -> bool {
         // Relevant code that implement this behavior in Python code:
         // basefilectx.cmp, filelog.size, storageutil.filerevisioncopied,
         // revlog.size, revlog.rawsize
 
         // Let’s call `file_data_len` what would be returned by
         // `self.data().file_data().len()`.
 
         if self.0.is_censored() {
             let file_data_len = 0;
             return other_len != file_data_len;
         }
 
         if self.0.has_length_affecting_flag_processor() {
             // We can’t conclude anything about `file_data_len`.
             return false;
         }
 
         // Revlog revisions (usually) have metadata for the size of
         // their data after decompression and delta resolution
         // as would be returned by `Revlog::get_rev_data`.
         //
         // For filelogs this is the file’s contents preceded by an optional
         // metadata block.
         let uncompressed_len = if let Some(l) = self.0.uncompressed_len() {
             l as u64
         } else {
             // The field was set to -1, the actual uncompressed len is unknown.
             // We need to decompress to say more.
             return false;
         };
         // `uncompressed_len = file_data_len + optional_metadata_len`,
         // so `file_data_len <= uncompressed_len`.
         if uncompressed_len < other_len {
             // Transitively, `file_data_len < other_len`.
             // So `other_len != file_data_len` definitely.
             return true;
         }
 
         if uncompressed_len == other_len + 4 {
             // It’s possible that `file_data_len == other_len` with an empty
             // metadata block (2 start marker bytes + 2 end marker bytes).
             // This happens when there wouldn’t otherwise be metadata, but
             // the first 2 bytes of file data happen to match a start marker
             // and would be ambiguous.
             return false;
         }
 
         if !self.0.has_p1() {
             // There may or may not be copy metadata, so we can’t deduce more
             // about `file_data_len` without computing file data.
             return false;
         }
 
         // Filelog ancestry is not meaningful in the way changelog ancestry is.
         // It only provides hints to delta generation.
         // p1 and p2 are set to null when making a copy or rename since
         // contents are likely unrelatedto what might have previously existed
         // at the destination path.
         //
         // Conversely, since here p1 is non-null, there is no copy metadata.
         // Note that this reasoning may be invalidated in the presence of
         // merges made by some previous versions of Mercurial that
         // swapped p1 and p2. See <https://bz.mercurial-scm.org/show_bug.cgi?id=6528>
         // and `tests/test-issue6528.t`.
         //
         // Since copy metadata is currently the only kind of metadata
         // kept in revlog data of filelogs,
         // this `FilelogEntry` does not have such metadata:
         let file_data_len = uncompressed_len;
 
         file_data_len != other_len
     }
 
     pub fn data(&self) -> Result<FilelogRevisionData, HgError> {
         let data = self.0.data();
         match data {
             Ok(data) => Ok(FilelogRevisionData(data.into_owned())),
             // Errors other than `HgError` should not happen at this point
             Err(e) => match e {
                 RevlogError::Other(hg_error) => Err(hg_error),
                 revlog_error => Err(HgError::abort(
                     revlog_error.to_string(),
                     exit_codes::ABORT,
                     None,
                 )),
             },
         }
     }
 }
 
 /// The data for one revision in a filelog, uncompressed and delta-resolved.
 pub struct FilelogRevisionData(Vec<u8>);
 
 impl FilelogRevisionData {
     /// Split into metadata and data
     pub fn split(&self) -> Result<(Option<&[u8]>, &[u8]), HgError> {
         const DELIMITER: &[u8; 2] = &[b'\x01', b'\n'];
 
         if let Some(rest) = self.0.drop_prefix(DELIMITER) {
             if let Some((metadata, data)) = rest.split_2_by_slice(DELIMITER) {
                 Ok((Some(metadata), data))
             } else {
                 Err(HgError::corrupted(
                     "Missing metadata end delimiter in filelog entry",
                 ))
             }
         } else {
             Ok((None, &self.0))
         }
     }
 
     /// Returns the file contents at this revision, stripped of any metadata
     pub fn file_data(&self) -> Result<&[u8], HgError> {
         let (_metadata, data) = self.split()?;
         Ok(data)
     }
 
     /// Consume the entry, and convert it into data, discarding any metadata,
     /// if present.
     pub fn into_file_data(self) -> Result<Vec<u8>, HgError> {
         if let (Some(_metadata), data) = self.split()? {
             Ok(data.to_owned())
         } else {
             Ok(self.0)
         }
     }
 }

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

@@ -1,622 +1,639 b''
 use std::fmt::Debug;
 use std::ops::Deref;
 
 use byteorder::{BigEndian, ByteOrder};
 
 use crate::errors::HgError;
 use crate::revlog::node::Node;
 use crate::revlog::{Revision, NULL_REVISION};
-use crate::UncheckedRevision;
+use crate::{Graph, GraphError, RevlogIndex, UncheckedRevision};
 
 pub const INDEX_ENTRY_SIZE: usize = 64;
 
 pub struct IndexHeader {
     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])
     }
 
     const EMPTY_INDEX_HEADER: IndexHeader = IndexHeader {
         // We treat an empty file as a valid index with no entries.
         // Here we make an arbitrary choice of what we assume the format of the
         // index to be (V1, using generaldelta).
         // This doesn't matter too much, since we're only doing read-only
         // access. but the value corresponds to the `new_header` variable in
         // `revlog.py`, `_loadindex`
         header_bytes: [0, 3, 0, 1],
     };
 
     fn parse(index_bytes: &[u8]) -> Result<IndexHeader, HgError> {
         if index_bytes.is_empty() {
             return Ok(IndexHeader::EMPTY_INDEX_HEADER);
         }
         if index_bytes.len() < 4 {
             return Err(HgError::corrupted(
                 "corrupted revlog: can't read the index format header",
             ));
         }
         Ok(IndexHeader {
             header_bytes: {
                 let bytes: [u8; 4] =
                     index_bytes[0..4].try_into().expect("impossible");
                 bytes
             },
         })
     }
 }
 
 /// A Revlog index
 pub struct Index {
     bytes: Box<dyn Deref<Target = [u8]> + Send>,
     /// Offsets of starts of index blocks.
     /// Only needed when the index is interleaved with data.
     offsets: Option<Vec<usize>>,
     uses_generaldelta: bool,
 }
 
 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 {
+    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]),
+        }
+    }
+}
+
 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>,
     ) -> Result<Self, HgError> {
         let header = IndexHeader::parse(bytes.as_ref())?;
 
         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,
                     offsets: Some(offsets),
                     uses_generaldelta,
                 })
             } else {
                 Err(HgError::corrupted("unexpected inline revlog length"))
             }
         } else {
             Ok(Self {
                 bytes,
                 offsets: None,
                 uses_generaldelta,
             })
         }
     }
 
     pub fn uses_generaldelta(&self) -> bool {
         self.uses_generaldelta
     }
 
     /// Value of the inline flag.
     pub fn is_inline(&self) -> bool {
         self.offsets.is_some()
     }
 
     /// 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.offsets {
             offsets.len()
         } else {
             self.bytes.len() / INDEX_ENTRY_SIZE
         }
     }
 
     /// 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 if it
     /// exists.
     pub fn get_entry(&self, rev: Revision) -> Option<IndexEntry> {
         if rev == NULL_REVISION {
             return None;
         }
         Some(if let Some(offsets) = &self.offsets {
             self.get_entry_inline(rev, offsets)
         } else {
             self.get_entry_separated(rev)
         })
     }
 
     fn get_entry_inline(
         &self,
         rev: Revision,
         offsets: &[usize],
     ) -> IndexEntry {
         let start = offsets[rev 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 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 == 0 { Some(0) } else { None };
 
         IndexEntry {
             bytes,
             offset_override,
         }
     }
 }
 
 impl super::RevlogIndex for Index {
     fn len(&self) -> usize {
         self.len()
     }
 
     fn node(&self, rev: Revision) -> Option<&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 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()
     }
 }
 
 #[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: 0,
                 link_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.to_be_bytes(),
             );
             bytes.extend(&self.link_revision.to_be_bytes());
             bytes.extend(&self.p1.to_be_bytes());
             bytes.extend(&self.p2.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")
             .format_flags()
             .is_inline()
     }
 
     pub fn uses_generaldelta(index_bytes: &[u8]) -> bool {
         IndexHeader::parse(index_bytes)
             .expect("too short")
             .format_flags()
             .uses_generaldelta()
     }
 
     pub fn get_version(index_bytes: &[u8]) -> u16 {
         IndexHeader::parse(index_bytes)
             .expect("too short")
             .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(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(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(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(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-core/src/revlog/manifest.rs

@@ -1,203 +1,209 b''
 use crate::errors::HgError;
 use crate::revlog::{Node, NodePrefix};
 use crate::revlog::{Revlog, RevlogError};
 use crate::utils::hg_path::HgPath;
 use crate::utils::SliceExt;
 use crate::vfs::Vfs;
-use crate::{Revision, UncheckedRevision};
+use crate::{Graph, GraphError, Revision, UncheckedRevision};
 
 /// A specialized `Revlog` to work with `manifest` data format.
 pub struct Manifestlog {
     /// The generic `revlog` format.
     revlog: Revlog,
 }
 
+impl Graph for Manifestlog {
+    fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
+        self.revlog.parents(rev)
+    }
+}
+
 impl Manifestlog {
     /// Open the `manifest` of a repository given by its root.
     pub fn open(store_vfs: &Vfs, use_nodemap: bool) -> Result<Self, HgError> {
         let revlog =
             Revlog::open(store_vfs, "00manifest.i", None, use_nodemap)?;
         Ok(Self { revlog })
     }
 
     /// Return the `Manifest` for the given node ID.
     ///
     /// Note: this is a node ID in the manifestlog, typically found through
     /// `ChangelogEntry::manifest_node`. It is *not* the node ID of any
     /// changeset.
     ///
     /// See also `Repo::manifest_for_node`
     pub fn data_for_node(
         &self,
         node: NodePrefix,
     ) -> Result<Manifest, RevlogError> {
         let rev = self.revlog.rev_from_node(node)?;
         self.data_for_checked_rev(rev)
     }
 
     /// Return the `Manifest` of a given revision number.
     ///
     /// Note: this is a revision number in the manifestlog, *not* of any
     /// changeset.
     ///
     /// See also `Repo::manifest_for_rev`
     pub fn data_for_rev(
         &self,
         rev: UncheckedRevision,
     ) -> Result<Manifest, RevlogError> {
         let bytes = self.revlog.get_rev_data(rev)?.into_owned();
         Ok(Manifest { bytes })
     }
 
     pub fn data_for_checked_rev(
         &self,
         rev: Revision,
     ) -> Result<Manifest, RevlogError> {
         let bytes =
             self.revlog.get_rev_data_for_checked_rev(rev)?.into_owned();
         Ok(Manifest { bytes })
     }
 }
 
 /// `Manifestlog` entry which knows how to interpret the `manifest` data bytes.
 #[derive(Debug)]
 pub struct Manifest {
     /// Format for a manifest: flat sequence of variable-size entries,
     /// sorted by path, each as:
     ///
     /// ```text
     /// <path> \0 <hex_node_id> <flags> \n
     /// ```
     ///
     /// The last entry is also terminated by a newline character.
     /// Flags is one of `b""` (the empty string), `b"x"`, `b"l"`, or `b"t"`.
     bytes: Vec<u8>,
 }
 
 impl Manifest {
     pub fn iter(
         &self,
     ) -> impl Iterator<Item = Result<ManifestEntry, HgError>> {
         self.bytes
             .split(|b| b == &b'\n')
             .filter(|line| !line.is_empty())
             .map(ManifestEntry::from_raw)
     }
 
     /// If the given path is in this manifest, return its filelog node ID
     pub fn find_by_path(
         &self,
         path: &HgPath,
     ) -> Result<Option<ManifestEntry>, HgError> {
         use std::cmp::Ordering::*;
         let path = path.as_bytes();
         // Both boundaries of this `&[u8]` slice are always at the boundary of
         // an entry
         let mut bytes = &*self.bytes;
 
         // Binary search algorithm derived from `[T]::binary_search_by`
         // <https://github.com/rust-lang/rust/blob/1.57.0/library/core/src/slice/mod.rs#L2221>
         // except we don’t have a slice of entries. Instead we jump to the
         // middle of the byte slice and look around for entry delimiters
         // (newlines).
         while let Some(entry_range) = Self::find_entry_near_middle_of(bytes)? {
             let (entry_path, rest) =
                 ManifestEntry::split_path(&bytes[entry_range.clone()])?;
             let cmp = entry_path.cmp(path);
             if cmp == Less {
                 let after_newline = entry_range.end + 1;
                 bytes = &bytes[after_newline..];
             } else if cmp == Greater {
                 bytes = &bytes[..entry_range.start];
             } else {
                 return Ok(Some(ManifestEntry::from_path_and_rest(
                     entry_path, rest,
                 )));
             }
         }
         Ok(None)
     }
 
     /// If there is at least one, return the byte range of an entry *excluding*
     /// the final newline.
     fn find_entry_near_middle_of(
         bytes: &[u8],
     ) -> Result<Option<std::ops::Range<usize>>, HgError> {
         let len = bytes.len();
         if len > 0 {
             let middle = bytes.len() / 2;
             // Integer division rounds down, so `middle < len`.
             let (before, after) = bytes.split_at(middle);
             let is_newline = |&byte: &u8| byte == b'\n';
             let entry_start = match before.iter().rposition(is_newline) {
                 Some(i) => i + 1,
                 None => 0, // We choose the first entry in `bytes`
             };
             let entry_end = match after.iter().position(is_newline) {
                 Some(i) => {
                     // No `+ 1` here to exclude this newline from the range
                     middle + i
                 }
                 None => {
                     // In a well-formed manifest:
                     //
                     // * Since `len > 0`, `bytes` contains at least one entry
                     // * Every entry ends with a newline
                     // * Since `middle < len`, `after` contains at least the
                     //   newline at the end of the last entry of `bytes`.
                     //
                     // We didn’t find a newline, so this manifest is not
                     // well-formed.
                     return Err(HgError::corrupted(
                         "manifest entry without \\n delimiter",
                     ));
                 }
             };
             Ok(Some(entry_start..entry_end))
         } else {
             // len == 0
             Ok(None)
         }
     }
 }
 
 /// `Manifestlog` entry which knows how to interpret the `manifest` data bytes.
 #[derive(Debug)]
 pub struct ManifestEntry<'manifest> {
     pub path: &'manifest HgPath,
     pub hex_node_id: &'manifest [u8],
 
     /// `Some` values are b'x', b'l', or 't'
     pub flags: Option<u8>,
 }
 
 impl<'a> ManifestEntry<'a> {
     fn split_path(bytes: &[u8]) -> Result<(&[u8], &[u8]), HgError> {
         bytes.split_2(b'\0').ok_or_else(|| {
             HgError::corrupted("manifest entry without \\0 delimiter")
         })
     }
 
     fn from_path_and_rest(path: &'a [u8], rest: &'a [u8]) -> Self {
         let (hex_node_id, flags) = match rest.split_last() {
             Some((&b'x', rest)) => (rest, Some(b'x')),
             Some((&b'l', rest)) => (rest, Some(b'l')),
             Some((&b't', rest)) => (rest, Some(b't')),
             _ => (rest, None),
         };
         Self {
             path: HgPath::new(path),
             hex_node_id,
             flags,
         }
     }
 
     fn from_raw(bytes: &'a [u8]) -> Result<Self, HgError> {
         let (path, rest) = Self::split_path(bytes)?;
         Ok(Self::from_path_and_rest(path, rest))
     }
 
     pub fn node_id(&self) -> Result<Node, HgError> {
         Node::from_hex_for_repo(self.hex_node_id)
     }
 }

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

@@ -1,904 +1,910 b''
 // Copyright 2018-2023 Georges Racinet <[e-mail]>
 //           and Mercurial contributors
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 //! Mercurial concepts for handling revision history
 
 pub mod node;
 pub mod nodemap;
 mod nodemap_docket;
 pub mod path_encode;
 pub use node::{FromHexError, Node, NodePrefix};
 pub mod changelog;
 pub mod filelog;
 pub mod index;
 pub mod manifest;
 pub mod patch;
 
 use std::borrow::Cow;
 use std::io::Read;
 use std::ops::Deref;
 use std::path::Path;
 
 use flate2::read::ZlibDecoder;
 use sha1::{Digest, Sha1};
 use std::cell::RefCell;
 use zstd;
 
 use self::node::{NODE_BYTES_LENGTH, NULL_NODE};
 use self::nodemap_docket::NodeMapDocket;
 use super::index::Index;
 use super::nodemap::{NodeMap, NodeMapError};
 use crate::errors::HgError;
 use crate::vfs::Vfs;
 
 /// Mercurial revision numbers
 ///
 /// As noted in revlog.c, revision numbers are actually encoded in
 /// 4 bytes, and are liberally converted to ints, whence the i32
 pub type Revision = i32;
 
 /// Unchecked Mercurial revision numbers.
 ///
 /// Values of this type have no guarantee of being a valid revision number
 /// in any context. Use method `check_revision` to get a valid revision within
 /// the appropriate index object.
 ///
 /// As noted in revlog.c, revision numbers are actually encoded in
 /// 4 bytes, and are liberally converted to ints, whence the i32
 #[derive(
     Debug,
     derive_more::Display,
     Clone,
     Copy,
     Hash,
     PartialEq,
     Eq,
     PartialOrd,
     Ord,
 )]
 pub struct UncheckedRevision(i32);
 
 impl From<Revision> for UncheckedRevision {
     fn from(value: Revision) -> Self {
         Self(value)
     }
 }
 
 /// Marker expressing the absence of a parent
 ///
 /// Independently of the actual representation, `NULL_REVISION` is guaranteed
 /// to be smaller than all existing revisions.
 pub const NULL_REVISION: Revision = -1;
 
 /// Same as `mercurial.node.wdirrev`
 ///
 /// This is also equal to `i32::max_value()`, but it's better to spell
 /// it out explicitely, same as in `mercurial.node`
 #[allow(clippy::unreadable_literal)]
 pub const WORKING_DIRECTORY_REVISION: UncheckedRevision =
     UncheckedRevision(0x7fffffff);
 
 pub const WORKING_DIRECTORY_HEX: &str =
     "ffffffffffffffffffffffffffffffffffffffff";
 
 /// The simplest expression of what we need of Mercurial DAGs.
 pub trait Graph {
     /// Return the two parents of the given `Revision`.
     ///
     /// Each of the parents can be independently `NULL_REVISION`
     fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError>;
 }
 
 #[derive(Clone, Debug, PartialEq)]
 pub enum GraphError {
     ParentOutOfRange(Revision),
 }
 
 /// The Mercurial Revlog Index
 ///
 /// This is currently limited to the minimal interface that is needed for
 /// the [`nodemap`](nodemap/index.html) module
 pub trait RevlogIndex {
     /// Total number of Revisions referenced in this index
     fn len(&self) -> usize;
 
     fn is_empty(&self) -> bool {
         self.len() == 0
     }
 
     /// Return a reference to the Node or `None` for `NULL_REVISION`
     fn node(&self, rev: Revision) -> Option<&Node>;
 
     /// Return a [`Revision`] if `rev` is a valid revision number for this
     /// index
     fn check_revision(&self, rev: UncheckedRevision) -> Option<Revision> {
         let rev = rev.0;
 
         if rev == NULL_REVISION || (rev >= 0 && (rev as usize) < self.len()) {
             Some(rev)
         } else {
             None
         }
     }
 }
 
 const REVISION_FLAG_CENSORED: u16 = 1 << 15;
 const REVISION_FLAG_ELLIPSIS: u16 = 1 << 14;
 const REVISION_FLAG_EXTSTORED: u16 = 1 << 13;
 const REVISION_FLAG_HASCOPIESINFO: u16 = 1 << 12;
 
 // Keep this in sync with REVIDX_KNOWN_FLAGS in
 // mercurial/revlogutils/flagutil.py
 const REVIDX_KNOWN_FLAGS: u16 = REVISION_FLAG_CENSORED
     | REVISION_FLAG_ELLIPSIS
     | REVISION_FLAG_EXTSTORED
     | REVISION_FLAG_HASCOPIESINFO;
 
 const NULL_REVLOG_ENTRY_FLAGS: u16 = 0;
 
 #[derive(Debug, derive_more::From, derive_more::Display)]
 pub enum RevlogError {
     InvalidRevision,
     /// Working directory is not supported
     WDirUnsupported,
     /// Found more than one entry whose ID match the requested prefix
     AmbiguousPrefix,
     #[from]
     Other(HgError),
 }
 
 impl From<NodeMapError> for RevlogError {
     fn from(error: NodeMapError) -> Self {
         match error {
             NodeMapError::MultipleResults => RevlogError::AmbiguousPrefix,
             NodeMapError::RevisionNotInIndex(rev) => RevlogError::corrupted(
                 format!("nodemap point to revision {} not in index", rev),
             ),
         }
     }
 }
 
 fn corrupted<S: AsRef<str>>(context: S) -> HgError {
     HgError::corrupted(format!("corrupted revlog, {}", context.as_ref()))
 }
 
 impl RevlogError {
     fn corrupted<S: AsRef<str>>(context: S) -> Self {
         RevlogError::Other(corrupted(context))
     }
 }
 
 /// Read only implementation of revlog.
 pub struct Revlog {
     /// When index and data are not interleaved: bytes of the revlog index.
     /// When index and data are interleaved: bytes of the revlog index and
     /// data.
     index: Index,
     /// When index and data are not interleaved: bytes of the revlog data
     data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>>,
     /// When present on disk: the persistent nodemap for this revlog
     nodemap: Option<nodemap::NodeTree>,
 }
 
+impl Graph for Revlog {
+    fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
+        self.index.parents(rev)
+    }
+}
+
 impl Revlog {
     /// Open a revlog index file.
     ///
     /// It will also open the associated data file if index and data are not
     /// interleaved.
     pub fn open(
         store_vfs: &Vfs,
         index_path: impl AsRef<Path>,
         data_path: Option<&Path>,
         use_nodemap: bool,
     ) -> Result<Self, HgError> {
         let index_path = index_path.as_ref();
         let index = {
             match store_vfs.mmap_open_opt(&index_path)? {
                 None => Index::new(Box::new(vec![])),
                 Some(index_mmap) => {
                     let index = Index::new(Box::new(index_mmap))?;
                     Ok(index)
                 }
             }
         }?;
 
         let default_data_path = index_path.with_extension("d");
 
         // type annotation required
         // won't recognize Mmap as Deref<Target = [u8]>
         let data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>> =
             if index.is_inline() {
                 None
             } else {
                 let data_path = data_path.unwrap_or(&default_data_path);
                 let data_mmap = store_vfs.mmap_open(data_path)?;
                 Some(Box::new(data_mmap))
             };
 
         let nodemap = if index.is_inline() || !use_nodemap {
             None
         } else {
             NodeMapDocket::read_from_file(store_vfs, index_path)?.map(
                 |(docket, data)| {
                     nodemap::NodeTree::load_bytes(
                         Box::new(data),
                         docket.data_length,
                     )
                 },
             )
         };
 
         Ok(Revlog {
             index,
             data_bytes,
             nodemap,
         })
     }
 
     /// Return number of entries of the `Revlog`.
     pub fn len(&self) -> usize {
         self.index.len()
     }
 
     /// Returns `true` if the `Revlog` has zero `entries`.
     pub fn is_empty(&self) -> bool {
         self.index.is_empty()
     }
 
     /// Returns the node ID for the given revision number, if it exists in this
     /// revlog
     pub fn node_from_rev(&self, rev: UncheckedRevision) -> Option<&Node> {
         if rev == NULL_REVISION.into() {
             return Some(&NULL_NODE);
         }
         let rev = self.index.check_revision(rev)?;
         Some(self.index.get_entry(rev)?.hash())
     }
 
     /// Return the revision number for the given node ID, if it exists in this
     /// revlog
     pub fn rev_from_node(
         &self,
         node: NodePrefix,
     ) -> Result<Revision, RevlogError> {
         let looked_up = if let Some(nodemap) = &self.nodemap {
             nodemap
                 .find_bin(&self.index, node)?
                 .ok_or(RevlogError::InvalidRevision)
         } else {
             self.rev_from_node_no_persistent_nodemap(node)
         };
 
         if node.is_prefix_of(&NULL_NODE) {
             return match looked_up {
                 Ok(_) => Err(RevlogError::AmbiguousPrefix),
                 Err(RevlogError::InvalidRevision) => Ok(NULL_REVISION),
                 res => res,
             };
         };
 
         looked_up
     }
 
     /// Same as `rev_from_node`, without using a persistent nodemap
     ///
     /// This is used as fallback when a persistent nodemap is not present.
     /// This happens when the persistent-nodemap experimental feature is not
     /// enabled, or for small revlogs.
     fn rev_from_node_no_persistent_nodemap(
         &self,
         node: NodePrefix,
     ) -> Result<Revision, RevlogError> {
         // Linear scan of the revlog
         // TODO: consider building a non-persistent nodemap in memory to
         // optimize these cases.
         let mut found_by_prefix = None;
         for rev in (0..self.len() as Revision).rev() {
             let index_entry = self.index.get_entry(rev).ok_or_else(|| {
                 HgError::corrupted(
                     "revlog references a revision not in the index",
                 )
             })?;
             if node == *index_entry.hash() {
                 return Ok(rev);
             }
             if node.is_prefix_of(index_entry.hash()) {
                 if found_by_prefix.is_some() {
                     return Err(RevlogError::AmbiguousPrefix);
                 }
                 found_by_prefix = Some(rev)
             }
         }
         found_by_prefix.ok_or(RevlogError::InvalidRevision)
     }
 
     /// Returns whether the given revision exists in this revlog.
     pub fn has_rev(&self, rev: UncheckedRevision) -> bool {
         self.index.check_revision(rev).is_some()
     }
 
     /// Return the full data associated to a revision.
     ///
     /// All entries required to build the final data out of deltas will be
     /// retrieved as needed, and the deltas will be applied to the inital
     /// snapshot to rebuild the final data.
     pub fn get_rev_data(
         &self,
         rev: UncheckedRevision,
     ) -> Result<Cow<[u8]>, RevlogError> {
         if rev == NULL_REVISION.into() {
             return Ok(Cow::Borrowed(&[]));
         };
         self.get_entry(rev)?.data()
     }
 
     /// [`Self::get_rev_data`] for checked revisions.
     pub fn get_rev_data_for_checked_rev(
         &self,
         rev: Revision,
     ) -> Result<Cow<[u8]>, RevlogError> {
         if rev == NULL_REVISION {
             return Ok(Cow::Borrowed(&[]));
         };
         self.get_entry_for_checked_rev(rev)?.data()
     }
 
     /// Check the hash of some given data against the recorded hash.
     pub fn check_hash(
         &self,
         p1: Revision,
         p2: Revision,
         expected: &[u8],
         data: &[u8],
     ) -> bool {
         let e1 = self.index.get_entry(p1);
         let h1 = match e1 {
             Some(ref entry) => entry.hash(),
             None => &NULL_NODE,
         };
         let e2 = self.index.get_entry(p2);
         let h2 = match e2 {
             Some(ref entry) => entry.hash(),
             None => &NULL_NODE,
         };
 
         hash(data, h1.as_bytes(), h2.as_bytes()) == expected
     }
 
     /// Build the full data of a revision out its snapshot
     /// and its deltas.
     fn build_data_from_deltas(
         snapshot: RevlogEntry,
         deltas: &[RevlogEntry],
     ) -> Result<Vec<u8>, HgError> {
         let snapshot = snapshot.data_chunk()?;
         let deltas = deltas
             .iter()
             .rev()
             .map(RevlogEntry::data_chunk)
             .collect::<Result<Vec<_>, _>>()?;
         let patches: Vec<_> =
             deltas.iter().map(|d| patch::PatchList::new(d)).collect();
         let patch = patch::fold_patch_lists(&patches);
         Ok(patch.apply(&snapshot))
     }
 
     /// Return the revlog data.
     fn data(&self) -> &[u8] {
         match &self.data_bytes {
             Some(data_bytes) => data_bytes,
             None => panic!(
                 "forgot to load the data or trying to access inline data"
             ),
         }
     }
 
     pub fn make_null_entry(&self) -> RevlogEntry {
         RevlogEntry {
             revlog: self,
             rev: NULL_REVISION,
             bytes: b"",
             compressed_len: 0,
             uncompressed_len: 0,
             base_rev_or_base_of_delta_chain: None,
             p1: NULL_REVISION,
             p2: NULL_REVISION,
             flags: NULL_REVLOG_ENTRY_FLAGS,
             hash: NULL_NODE,
         }
     }
 
     fn get_entry_for_checked_rev(
         &self,
         rev: Revision,
     ) -> Result<RevlogEntry, RevlogError> {
         if rev == NULL_REVISION {
             return Ok(self.make_null_entry());
         }
         let index_entry = self
             .index
             .get_entry(rev)
             .ok_or(RevlogError::InvalidRevision)?;
         let start = index_entry.offset();
         let end = start + index_entry.compressed_len() as usize;
         let data = if self.index.is_inline() {
             self.index.data(start, end)
         } else {
             &self.data()[start..end]
         };
         let base_rev = self
             .index
             .check_revision(index_entry.base_revision_or_base_of_delta_chain())
             .ok_or_else(|| {
                 RevlogError::corrupted(format!(
                     "base revision for rev {} is invalid",
                     rev
                 ))
             })?;
         let p1 =
             self.index.check_revision(index_entry.p1()).ok_or_else(|| {
                 RevlogError::corrupted(format!(
                     "p1 for rev {} is invalid",
                     rev
                 ))
             })?;
         let p2 =
             self.index.check_revision(index_entry.p2()).ok_or_else(|| {
                 RevlogError::corrupted(format!(
                     "p2 for rev {} is invalid",
                     rev
                 ))
             })?;
         let entry = RevlogEntry {
             revlog: self,
             rev,
             bytes: data,
             compressed_len: index_entry.compressed_len(),
             uncompressed_len: index_entry.uncompressed_len(),
             base_rev_or_base_of_delta_chain: if base_rev == rev {
                 None
             } else {
                 Some(base_rev)
             },
             p1,
             p2,
             flags: index_entry.flags(),
             hash: *index_entry.hash(),
         };
         Ok(entry)
     }
 
     /// Get an entry of the revlog.
     pub fn get_entry(
         &self,
         rev: UncheckedRevision,
     ) -> Result<RevlogEntry, RevlogError> {
         if rev == NULL_REVISION.into() {
             return Ok(self.make_null_entry());
         }
         let rev = self.index.check_revision(rev).ok_or_else(|| {
             RevlogError::corrupted(format!("rev {} is invalid", rev))
         })?;
         self.get_entry_for_checked_rev(rev)
     }
 }
 
 /// The revlog entry's bytes and the necessary informations to extract
 /// the entry's data.
 #[derive(Clone)]
 pub struct RevlogEntry<'revlog> {
     revlog: &'revlog Revlog,
     rev: Revision,
     bytes: &'revlog [u8],
     compressed_len: u32,
     uncompressed_len: i32,
     base_rev_or_base_of_delta_chain: Option<Revision>,
     p1: Revision,
     p2: Revision,
     flags: u16,
     hash: Node,
 }
 
 thread_local! {
   // seems fine to [unwrap] here: this can only fail due to memory allocation
   // failing, and it's normal for that to cause panic.
   static ZSTD_DECODER : RefCell<zstd::bulk::Decompressor<'static>> =
       RefCell::new(zstd::bulk::Decompressor::new().ok().unwrap());
 }
 
 fn zstd_decompress_to_buffer(
     bytes: &[u8],
     buf: &mut Vec<u8>,
 ) -> Result<usize, std::io::Error> {
     ZSTD_DECODER
         .with(|decoder| decoder.borrow_mut().decompress_to_buffer(bytes, buf))
 }
 
 impl<'revlog> RevlogEntry<'revlog> {
     pub fn revision(&self) -> Revision {
         self.rev
     }
 
     pub fn node(&self) -> &Node {
         &self.hash
     }
 
     pub fn uncompressed_len(&self) -> Option<u32> {
         u32::try_from(self.uncompressed_len).ok()
     }
 
     pub fn has_p1(&self) -> bool {
         self.p1 != NULL_REVISION
     }
 
     pub fn p1_entry(
         &self,
     ) -> Result<Option<RevlogEntry<'revlog>>, RevlogError> {
         if self.p1 == NULL_REVISION {
             Ok(None)
         } else {
             Ok(Some(self.revlog.get_entry_for_checked_rev(self.p1)?))
         }
     }
 
     pub fn p2_entry(
         &self,
     ) -> Result<Option<RevlogEntry<'revlog>>, RevlogError> {
         if self.p2 == NULL_REVISION {
             Ok(None)
         } else {
             Ok(Some(self.revlog.get_entry_for_checked_rev(self.p2)?))
         }
     }
 
     pub fn p1(&self) -> Option<Revision> {
         if self.p1 == NULL_REVISION {
             None
         } else {
             Some(self.p1)
         }
     }
 
     pub fn p2(&self) -> Option<Revision> {
         if self.p2 == NULL_REVISION {
             None
         } else {
             Some(self.p2)
         }
     }
 
     pub fn is_censored(&self) -> bool {
         (self.flags & REVISION_FLAG_CENSORED) != 0
     }
 
     pub fn has_length_affecting_flag_processor(&self) -> bool {
         // Relevant Python code: revlog.size()
         // note: ELLIPSIS is known to not change the content
         (self.flags & (REVIDX_KNOWN_FLAGS ^ REVISION_FLAG_ELLIPSIS)) != 0
     }
 
     /// The data for this entry, after resolving deltas if any.
     pub fn rawdata(&self) -> Result<Cow<'revlog, [u8]>, RevlogError> {
         let mut entry = self.clone();
         let mut delta_chain = vec![];
 
         // The meaning of `base_rev_or_base_of_delta_chain` depends on
         // generaldelta. See the doc on `ENTRY_DELTA_BASE` in
         // `mercurial/revlogutils/constants.py` and the code in
         // [_chaininfo] and in [index_deltachain].
         let uses_generaldelta = self.revlog.index.uses_generaldelta();
         while let Some(base_rev) = entry.base_rev_or_base_of_delta_chain {
             entry = if uses_generaldelta {
                 delta_chain.push(entry);
                 self.revlog.get_entry_for_checked_rev(base_rev)?
             } else {
                 let base_rev = UncheckedRevision(entry.rev - 1);
                 delta_chain.push(entry);
                 self.revlog.get_entry(base_rev)?
             };
         }
 
         let data = if delta_chain.is_empty() {
             entry.data_chunk()?
         } else {
             Revlog::build_data_from_deltas(entry, &delta_chain)?.into()
         };
 
         Ok(data)
     }
 
     fn check_data(
         &self,
         data: Cow<'revlog, [u8]>,
     ) -> Result<Cow<'revlog, [u8]>, RevlogError> {
         if self.revlog.check_hash(
             self.p1,
             self.p2,
             self.hash.as_bytes(),
             &data,
         ) {
             Ok(data)
         } else {
             if (self.flags & REVISION_FLAG_ELLIPSIS) != 0 {
                 return Err(HgError::unsupported(
                     "ellipsis revisions are not supported by rhg",
                 )
                 .into());
             }
             Err(corrupted(format!(
                 "hash check failed for revision {}",
                 self.rev
             ))
             .into())
         }
     }
 
     pub fn data(&self) -> Result<Cow<'revlog, [u8]>, RevlogError> {
         let data = self.rawdata()?;
         if self.rev == NULL_REVISION {
             return Ok(data);
         }
         if self.is_censored() {
             return Err(HgError::CensoredNodeError.into());
         }
         self.check_data(data)
     }
 
     /// Extract the data contained in the entry.
     /// This may be a delta. (See `is_delta`.)
     fn data_chunk(&self) -> Result<Cow<'revlog, [u8]>, HgError> {
         if self.bytes.is_empty() {
             return Ok(Cow::Borrowed(&[]));
         }
         match self.bytes[0] {
             // Revision data is the entirety of the entry, including this
             // header.
             b'\0' => Ok(Cow::Borrowed(self.bytes)),
             // Raw revision data follows.
             b'u' => Ok(Cow::Borrowed(&self.bytes[1..])),
             // zlib (RFC 1950) data.
             b'x' => Ok(Cow::Owned(self.uncompressed_zlib_data()?)),
             // zstd data.
             b'\x28' => Ok(Cow::Owned(self.uncompressed_zstd_data()?)),
             // A proper new format should have had a repo/store requirement.
             format_type => Err(corrupted(format!(
                 "unknown compression header '{}'",
                 format_type
             ))),
         }
     }
 
     fn uncompressed_zlib_data(&self) -> Result<Vec<u8>, HgError> {
         let mut decoder = ZlibDecoder::new(self.bytes);
         if self.is_delta() {
             let mut buf = Vec::with_capacity(self.compressed_len as usize);
             decoder
                 .read_to_end(&mut buf)
                 .map_err(|e| corrupted(e.to_string()))?;
             Ok(buf)
         } else {
             let cap = self.uncompressed_len.max(0) as usize;
             let mut buf = vec![0; cap];
             decoder
                 .read_exact(&mut buf)
                 .map_err(|e| corrupted(e.to_string()))?;
             Ok(buf)
         }
     }
 
     fn uncompressed_zstd_data(&self) -> Result<Vec<u8>, HgError> {
         let cap = self.uncompressed_len.max(0) as usize;
         if self.is_delta() {
             // [cap] is usually an over-estimate of the space needed because
             // it's the length of delta-decoded data, but we're interested
             // in the size of the delta.
             // This means we have to [shrink_to_fit] to avoid holding on
             // to a large chunk of memory, but it also means we must have a
             // fallback branch, for the case when the delta is longer than
             // the original data (surprisingly, this does happen in practice)
             let mut buf = Vec::with_capacity(cap);
             match zstd_decompress_to_buffer(self.bytes, &mut buf) {
                 Ok(_) => buf.shrink_to_fit(),
                 Err(_) => {
                     buf.clear();
                     zstd::stream::copy_decode(self.bytes, &mut buf)
                         .map_err(|e| corrupted(e.to_string()))?;
                 }
             };
             Ok(buf)
         } else {
             let mut buf = Vec::with_capacity(cap);
             let len = zstd_decompress_to_buffer(self.bytes, &mut buf)
                 .map_err(|e| corrupted(e.to_string()))?;
             if len != self.uncompressed_len as usize {
                 Err(corrupted("uncompressed length does not match"))
             } else {
                 Ok(buf)
             }
         }
     }
 
     /// Tell if the entry is a snapshot or a delta
     /// (influences on decompression).
     fn is_delta(&self) -> bool {
         self.base_rev_or_base_of_delta_chain.is_some()
     }
 }
 
 /// Calculate the hash of a revision given its data and its parents.
 fn hash(
     data: &[u8],
     p1_hash: &[u8],
     p2_hash: &[u8],
 ) -> [u8; NODE_BYTES_LENGTH] {
     let mut hasher = Sha1::new();
     let (a, b) = (p1_hash, p2_hash);
     if a > b {
         hasher.update(b);
         hasher.update(a);
     } else {
         hasher.update(a);
         hasher.update(b);
     }
     hasher.update(data);
     *hasher.finalize().as_ref()
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
     use crate::index::{IndexEntryBuilder, INDEX_ENTRY_SIZE};
     use itertools::Itertools;
 
     #[test]
     fn test_empty() {
         let temp = tempfile::tempdir().unwrap();
         let vfs = Vfs { base: temp.path() };
         std::fs::write(temp.path().join("foo.i"), b"").unwrap();
         let revlog = Revlog::open(&vfs, "foo.i", None, false).unwrap();
         assert!(revlog.is_empty());
         assert_eq!(revlog.len(), 0);
         assert!(revlog.get_entry(0.into()).is_err());
         assert!(!revlog.has_rev(0.into()));
         assert_eq!(
             revlog.rev_from_node(NULL_NODE.into()).unwrap(),
             NULL_REVISION
         );
         let null_entry = revlog.get_entry(NULL_REVISION.into()).ok().unwrap();
         assert_eq!(null_entry.revision(), NULL_REVISION);
         assert!(null_entry.data().unwrap().is_empty());
     }
 
     #[test]
     fn test_inline() {
         let temp = tempfile::tempdir().unwrap();
         let vfs = Vfs { base: temp.path() };
         let node0 = Node::from_hex("2ed2a3912a0b24502043eae84ee4b279c18b90dd")
             .unwrap();
         let node1 = Node::from_hex("b004912a8510032a0350a74daa2803dadfb00e12")
             .unwrap();
         let node2 = Node::from_hex("dd6ad206e907be60927b5a3117b97dffb2590582")
             .unwrap();
         let entry0_bytes = IndexEntryBuilder::new()
             .is_first(true)
             .with_version(1)
             .with_inline(true)
             .with_offset(INDEX_ENTRY_SIZE)
             .with_node(node0)
             .build();
         let entry1_bytes = IndexEntryBuilder::new()
             .with_offset(INDEX_ENTRY_SIZE)
             .with_node(node1)
             .build();
         let entry2_bytes = IndexEntryBuilder::new()
             .with_offset(INDEX_ENTRY_SIZE)
             .with_p1(0)
             .with_p2(1)
             .with_node(node2)
             .build();
         let contents = vec![entry0_bytes, entry1_bytes, entry2_bytes]
             .into_iter()
             .flatten()
             .collect_vec();
         std::fs::write(temp.path().join("foo.i"), contents).unwrap();
         let revlog = Revlog::open(&vfs, "foo.i", None, false).unwrap();
 
         let entry0 = revlog.get_entry(0.into()).ok().unwrap();
         assert_eq!(entry0.revision(), 0);
         assert_eq!(*entry0.node(), node0);
         assert!(!entry0.has_p1());
         assert_eq!(entry0.p1(), None);
         assert_eq!(entry0.p2(), None);
         let p1_entry = entry0.p1_entry().unwrap();
         assert!(p1_entry.is_none());
         let p2_entry = entry0.p2_entry().unwrap();
         assert!(p2_entry.is_none());
 
         let entry1 = revlog.get_entry(1.into()).ok().unwrap();
         assert_eq!(entry1.revision(), 1);
         assert_eq!(*entry1.node(), node1);
         assert!(!entry1.has_p1());
         assert_eq!(entry1.p1(), None);
         assert_eq!(entry1.p2(), None);
         let p1_entry = entry1.p1_entry().unwrap();
         assert!(p1_entry.is_none());
         let p2_entry = entry1.p2_entry().unwrap();
         assert!(p2_entry.is_none());
 
         let entry2 = revlog.get_entry(2.into()).ok().unwrap();
         assert_eq!(entry2.revision(), 2);
         assert_eq!(*entry2.node(), node2);
         assert!(entry2.has_p1());
         assert_eq!(entry2.p1(), Some(0));
         assert_eq!(entry2.p2(), Some(1));
         let p1_entry = entry2.p1_entry().unwrap();
         assert!(p1_entry.is_some());
         assert_eq!(p1_entry.unwrap().revision(), 0);
         let p2_entry = entry2.p2_entry().unwrap();
         assert!(p2_entry.is_some());
         assert_eq!(p2_entry.unwrap().revision(), 1);
     }
 
     #[test]
     fn test_nodemap() {
         let temp = tempfile::tempdir().unwrap();
         let vfs = Vfs { base: temp.path() };
 
         // building a revlog with a forced Node starting with zeros
         // This is a corruption, but it does not preclude using the nodemap
         // if we don't try and access the data
         let node0 = Node::from_hex("00d2a3912a0b24502043eae84ee4b279c18b90dd")
             .unwrap();
         let node1 = Node::from_hex("b004912a8510032a0350a74daa2803dadfb00e12")
             .unwrap();
         let entry0_bytes = IndexEntryBuilder::new()
             .is_first(true)
             .with_version(1)
             .with_inline(true)
             .with_offset(INDEX_ENTRY_SIZE)
             .with_node(node0)
             .build();
         let entry1_bytes = IndexEntryBuilder::new()
             .with_offset(INDEX_ENTRY_SIZE)
             .with_node(node1)
             .build();
         let contents = vec![entry0_bytes, entry1_bytes]
             .into_iter()
             .flatten()
             .collect_vec();
         std::fs::write(temp.path().join("foo.i"), contents).unwrap();
         let revlog = Revlog::open(&vfs, "foo.i", None, false).unwrap();
 
         // accessing the data shows the corruption
         revlog.get_entry(0.into()).unwrap().data().unwrap_err();
 
         assert_eq!(revlog.rev_from_node(NULL_NODE.into()).unwrap(), -1);
         assert_eq!(revlog.rev_from_node(node0.into()).unwrap(), 0);
         assert_eq!(revlog.rev_from_node(node1.into()).unwrap(), 1);
         assert_eq!(
             revlog
                 .rev_from_node(NodePrefix::from_hex("000").unwrap())
                 .unwrap(),
             -1
         );
         assert_eq!(
             revlog
                 .rev_from_node(NodePrefix::from_hex("b00").unwrap())
                 .unwrap(),
             1
         );
         // RevlogError does not implement PartialEq
         // (ultimately because io::Error does not)
         match revlog
             .rev_from_node(NodePrefix::from_hex("00").unwrap())
             .expect_err("Expected to give AmbiguousPrefix error")
         {
             RevlogError::AmbiguousPrefix => (),
             e => {
                 panic!("Got another error than AmbiguousPrefix: {:?}", e);
             }
         };
     }
 }