( )⚙ D11090 dirstate-v2: Rename Header to Root, move it to the end of the data file

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D11090

dirstate-v2: Rename Header to Root, move it to the end of the data file
ClosedPublic

Authored by SimonSapin on Jul 12 2021, 5:10 PM.

Details

Reviewers
Alphare
marmoute
Group Reviewers
hg-reviewers
Commits
rHG096ee2e260a3: dirstate-v2: Rename Header to Root, move it to the end of the data file
Summary

Now that they don’t have to be at the start, a given data file may contain
multiple "roots". A docket only points to one of them, and previous ones
are left unused to allow allow append-only in-place writing to an existing
data file.

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

SimonSapin created this revision.Jul 12 2021, 5:10 PM
baymax updated this revision to Diff 29220.Jul 12 2021, 6:39 PM

✅ refresh by Heptapod after a successful CI run (🐙 💚)

Alphare accepted this revision.Jul 13 2021, 11:10 AM
This revision is now accepted and ready to land.Jul 13 2021, 11:10 AM
marmoute added a subscriber: marmoute.Jul 16 2021, 5:54 AM
marmoute added inline comments.
rust/hg-core/src/dirstate_tree/on_disk.rs
5–15

strange char detected.

marmoute accepted this revision.Jul 16 2021, 5:55 AM
SimonSapin added inline comments.Jul 16 2021, 8:15 AM
rust/hg-core/src/dirstate_tree/on_disk.rs
5–15

I find it sad that Phabricator gets so upset over a perfectly normal non-breaking space in a comment, but having it here was not intentional so I’ll change it.

SimonSapin updated this revision to Diff 29332.Jul 16 2021, 8:37 AM
baymax updated this revision to Diff 29608.Jul 20 2021, 3:41 PM

✅ refresh by Heptapod after a successful CI run (🐙 💚)

Revision Contents
Changeset List

Diff 29217

rust/hg-core/src/dirstate_tree/on_disk.rs

//! The "version 2" disk representation of the dirstate //! The "version 2" disk representation of the dirstate
//! //!
//! # File format //! # File format
//! //!
//! The file starts with a fixed-sized header, whose layout is defined by the //! In dirstate-v2!format, the `.hg/dirstate` file is a "docket that starts
//! `Header` struct. Its `root` field contains the slice (offset and length) to //! with a fixed-sized header whose layout is defined by the `DocketHeader`
//! struct, followed by the data file identifier.
//!
//! A separate `.hg/dirstate.{uuid}.d` file contains most of the data. That
//! file may be longer than the size given in the docket, but not shorter. Only
//! the start of the data file up to the given size is considered. The
//! fixed-size "root" of the dirstate tree whose layout is defined by the
//! `Root` struct is found at the end of that slice of data.
//!
//! Its `root_nodes` field contains the slice (offset and length) to
marmouteUnsubmitted
Not Done

strange char detected.

marmoute: strange char detected.
SimonSapinAuthorUnsubmitted
Done

I find it sad that Phabricator gets so upset over a perfectly normal non-breaking space in a comment, but having it here was not intentional so I’ll change it.

SimonSapin: I find it sad that Phabricator gets so upset over a perfectly normal non-breaking space in a…
//! the nodes representing the files and directories at the root of the //! the nodes representing the files and directories at the root of the
//! repository. Each node is also fixed-size, defined by the `Node` struct. //! repository. Each node is also fixed-size, defined by the `Node` struct.
//! Nodes in turn contain slices to variable-size paths, and to their own child //! Nodes in turn contain slices to variable-size paths, and to their own child
//! nodes (if any) for nested files and directories. //! nodes (if any) for nested files and directories.
use crate::dirstate_tree::dirstate_map::{self, DirstateMap, NodeRef}; use crate::dirstate_tree::dirstate_map::{self, DirstateMap, NodeRef};
use crate::dirstate_tree::path_with_basename::WithBasename; use crate::dirstate_tree::path_with_basename::WithBasename;
use crate::errors::HgError; use crate::errors::HgError;
pub struct Docket<'on_disk> { pub struct Docket<'on_disk> {
header: &'on_disk DocketHeader, header: &'on_disk DocketHeader,
uuid: &'on_disk [u8], uuid: &'on_disk [u8],
} }
#[derive(BytesCast)] #[derive(BytesCast)]
#[repr(C)] #[repr(C)]
struct Header { struct Root {
root: ChildNodes, root_nodes: ChildNodes,
nodes_with_entry_count: Size, nodes_with_entry_count: Size,
nodes_with_copy_source_count: Size, nodes_with_copy_source_count: Size,
/// If non-zero, a hash of ignore files that were used for some previous /// If non-zero, a hash of ignore files that were used for some previous
/// run of the `status` algorithm. /// run of the `status` algorithm.
/// ///
/// We define: /// We define:
/// ///
/// - That timestamp was already strictly in the past when observed, /// - That timestamp was already strictly in the past when observed,
/// meaning that later changes cannot happen in the same clock tick /// meaning that later changes cannot happen in the same clock tick
/// and must cause a different modification time (unless the system /// and must cause a different modification time (unless the system
/// clock jumps back and we get unlucky, which is not impossible but /// clock jumps back and we get unlucky, which is not impossible but
/// but deemed unlikely enough). /// but deemed unlikely enough).
/// - All direct children of this directory (as returned by /// - All direct children of this directory (as returned by
/// `std::fs::read_dir`) either have a corresponding dirstate node, or /// `std::fs::read_dir`) either have a corresponding dirstate node, or
/// are ignored by ignore patterns whose hash is in /// are ignored by ignore patterns whose hash is in
/// `Header::ignore_patterns_hash`. /// `Root::ignore_patterns_hash`.
/// ///
/// This means that if `std::fs::symlink_metadata` later reports the /// This means that if `std::fs::symlink_metadata` later reports the
/// same modification time and ignored patterns haven’t changed, a run /// same modification time and ignored patterns haven’t changed, a run
/// of status that is not listing ignored files can skip calling /// of status that is not listing ignored files can skip calling
/// `std::fs::read_dir` again for this directory, iterate child /// `std::fs::read_dir` again for this directory, iterate child
/// dirstate nodes instead. /// dirstate nodes instead.
state: u8, state: u8,
data: Entry, data: Entry,
type PathSlice = Slice; type PathSlice = Slice;
/// Either nothing if `start == 0`, or a `HgPath` of `len` bytes /// Either nothing if `start == 0`, or a `HgPath` of `len` bytes
type OptPathSlice = Slice; type OptPathSlice = Slice;
/// Make sure that size-affecting changes are made knowingly /// Make sure that size-affecting changes are made knowingly
fn _static_assert_size_of() { fn _static_assert_size_of() {
let _ = std::mem::transmute::<DocketHeader, [u8; 81]>; let _ = std::mem::transmute::<DocketHeader, [u8; 81]>;
let _ = std::mem::transmute::<Header, [u8; 36]>; let _ = std::mem::transmute::<Root, [u8; 36]>;
let _ = std::mem::transmute::<Node, [u8; 49]>; let _ = std::mem::transmute::<Node, [u8; 49]>;
} }
/// Unexpected file format found in `.hg/dirstate` with the "v2" format. /// Unexpected file format found in `.hg/dirstate` with the "v2" format.
/// ///
/// This should only happen if Mercurial is buggy or a repository is corrupted. /// This should only happen if Mercurial is buggy or a repository is corrupted.
#[derive(Debug)] #[derive(Debug)]
pub struct DirstateV2ParseError; pub struct DirstateV2ParseError;
} }
pub(super) fn read<'on_disk>( pub(super) fn read<'on_disk>(
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
) -> Result<DirstateMap<'on_disk>, DirstateV2ParseError> { ) -> Result<DirstateMap<'on_disk>, DirstateV2ParseError> {
if on_disk.is_empty() { if on_disk.is_empty() {
return Ok(DirstateMap::empty(on_disk)); return Ok(DirstateMap::empty(on_disk));
} }
let (header, _) = // Find the `Root` at the end of the given slice
Header::from_bytes(on_disk).map_err(|_| DirstateV2ParseError)?; let root_offset = on_disk
.len()
.checked_sub(std::mem::size_of::<Root>())
// A non-empty slice too short is an error
.ok_or(DirstateV2ParseError)?;
let (root, _) = Root::from_bytes(&on_disk[root_offset..])
.map_err(|_| DirstateV2ParseError)?;
let dirstate_map = DirstateMap { let dirstate_map = DirstateMap {
on_disk, on_disk,
root: dirstate_map::ChildNodes::OnDisk(read_slice::<Node>( root: dirstate_map::ChildNodes::OnDisk(read_slice::<Node>(
on_disk, on_disk,
header.root, root.root_nodes,
)?), )?),
nodes_with_entry_count: header.nodes_with_entry_count.get(), nodes_with_entry_count: root.nodes_with_entry_count.get(),
nodes_with_copy_source_count: header nodes_with_copy_source_count: root.nodes_with_copy_source_count.get(),
.nodes_with_copy_source_count ignore_patterns_hash: root.ignore_patterns_hash,
.get(),
ignore_patterns_hash: header.ignore_patterns_hash,
}; };
Ok(dirstate_map) Ok(dirstate_map)
} }
impl Node { impl Node {
pub(super) fn full_path<'on_disk>( pub(super) fn full_path<'on_disk>(
&self, &self,
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
.map(|(slice, _rest)| slice) .map(|(slice, _rest)| slice)
.ok_or_else(|| DirstateV2ParseError) .ok_or_else(|| DirstateV2ParseError)
} }
pub(crate) fn for_each_tracked_path<'on_disk>( pub(crate) fn for_each_tracked_path<'on_disk>(
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
mut f: impl FnMut(&'on_disk HgPath), mut f: impl FnMut(&'on_disk HgPath),
) -> Result<(), DirstateV2ParseError> { ) -> Result<(), DirstateV2ParseError> {
let (header, _) = let (root, _) =
Header::from_bytes(on_disk).map_err(|_| DirstateV2ParseError)?; Root::from_bytes(on_disk).map_err(|_| DirstateV2ParseError)?;
fn recur<'on_disk>( fn recur<'on_disk>(
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
nodes: Slice, nodes: Slice,
f: &mut impl FnMut(&'on_disk HgPath), f: &mut impl FnMut(&'on_disk HgPath),
) -> Result<(), DirstateV2ParseError> { ) -> Result<(), DirstateV2ParseError> {
for node in read_slice::<Node>(on_disk, nodes)? { for node in read_slice::<Node>(on_disk, nodes)? {
if let Some(state) = node.state()? { if let Some(state) = node.state()? {
if state.is_tracked() { if state.is_tracked() {
f(node.full_path(on_disk)?) f(node.full_path(on_disk)?)
} }
} }
recur(on_disk, node.children, f)? recur(on_disk, node.children, f)?
} }
Ok(()) Ok(())
} }
recur(on_disk, header.root, &mut f) recur(on_disk, root.root_nodes, &mut f)
} }
pub(super) fn write( pub(super) fn write(
dirstate_map: &mut DirstateMap, dirstate_map: &mut DirstateMap,
) -> Result<Vec<u8>, DirstateError> { ) -> Result<Vec<u8>, DirstateError> {
let header_len = std::mem::size_of::<Header>(); let root_len = std::mem::size_of::<Root>();
// This ignores the space for paths, and for nodes without an entry. // This ignores the space for paths, and for nodes without an entry.
// TODO: better estimate? Skip the `Vec` and write to a file directly? // TODO: better estimate? Skip the `Vec` and write to a file directly?
let size_guess = header_len let size_guess = root_len
+ std::mem::size_of::<Node>() + std::mem::size_of::<Node>()
* dirstate_map.nodes_with_entry_count as usize; * dirstate_map.nodes_with_entry_count as usize;
let mut out = Vec::with_capacity(size_guess); let mut out = Vec::with_capacity(size_guess);
// Keep space for the header. We’ll fill it out at the end when we know the let root_nodes =
// actual offset for the root nodes.
out.resize(header_len, 0_u8);
let root =
write_nodes(dirstate_map, dirstate_map.root.as_ref(), &mut out)?; write_nodes(dirstate_map, dirstate_map.root.as_ref(), &mut out)?;
let header = Header { let root = Root {
root, root_nodes,
nodes_with_entry_count: dirstate_map.nodes_with_entry_count.into(), nodes_with_entry_count: dirstate_map.nodes_with_entry_count.into(),
nodes_with_copy_source_count: dirstate_map nodes_with_copy_source_count: dirstate_map
.nodes_with_copy_source_count .nodes_with_copy_source_count
.into(), .into(),
ignore_patterns_hash: dirstate_map.ignore_patterns_hash, ignore_patterns_hash: dirstate_map.ignore_patterns_hash,
}; };
out[..header_len].copy_from_slice(header.as_bytes()); out.extend(root.as_bytes());
Ok(out) Ok(out)
} }
fn write_nodes( fn write_nodes(
dirstate_map: &DirstateMap, dirstate_map: &DirstateMap,
nodes: dirstate_map::ChildNodesRef, nodes: dirstate_map::ChildNodesRef,
out: &mut Vec<u8>, out: &mut Vec<u8>,
) -> Result<ChildNodes, DirstateError> { ) -> Result<ChildNodes, DirstateError> {