( )⚙ D11558 dirstate-v2: Store a bitfield on disk instead of v1-like state

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D11558

dirstate-v2: Store a bitfield on disk instead of v1-like state
ClosedPublic

Authored by marmoute on Oct 1 2021, 2:40 PM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHGab5a7fdbf75c: dirstate-v2: Store a bitfield on disk instead of v1-like state

Diff Detail

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

Event Timeline

marmoute created this revision.Oct 1 2021, 2:40 PM
baymax updated this revision to Diff 30550.Oct 1 2021, 6:21 PM

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

Alphare accepted this revision.Oct 3 2021, 5:08 PM
Alphare added a subscriber: Alphare.
Alphare added inline comments.
rust/hg-core/src/dirstate/entry.rs
199

This would probably be more readable with a struct with named field, but it can be done in a follow-up.

This revision is now accepted and ready to land.Oct 3 2021, 5:08 PM

Revision Contents
Changeset List

Diff 30515

rust/hg-core/src/dirstate/entry.rs

Merged, Merged,
} }
/// The C implementation uses all signed types. This will be an issue /// The C implementation uses all signed types. This will be an issue
/// either when 4GB+ source files are commonplace or in 2038, whichever /// either when 4GB+ source files are commonplace or in 2038, whichever
/// comes first. /// comes first.
#[derive(Debug, PartialEq, Copy, Clone)] #[derive(Debug, PartialEq, Copy, Clone)]
pub struct DirstateEntry { pub struct DirstateEntry {
flags: Flags, pub(crate) flags: Flags,
mode_size: Option<(i32, i32)>, mode_size: Option<(i32, i32)>,
mtime: Option<i32>, mtime: Option<i32>,
} }
bitflags! { bitflags! {
struct Flags: u8 { pub(crate) struct Flags: u8 {
const WDIR_TRACKED = 1 << 0; const WDIR_TRACKED = 1 << 0;
const P1_TRACKED = 1 << 1; const P1_TRACKED = 1 << 1;
const P2_INFO = 1 << 2; const P2_INFO = 1 << 2;
} }
} }
pub const V1_RANGEMASK: i32 = 0x7FFFFFFF; pub const V1_RANGEMASK: i32 = 0x7FFFFFFF;
pub const MTIME_UNSET: i32 = -1; pub const MTIME_UNSET: i32 = -1;
/// A `DirstateEntry` with a size of `-2` means that it was merged from the /// A `DirstateEntry` with a size of `-2` means that it was merged from the
/// other parent. This allows revert to pick the right status back during a /// other parent. This allows revert to pick the right status back during a
/// merge. /// merge.
pub const SIZE_FROM_OTHER_PARENT: i32 = -2; pub const SIZE_FROM_OTHER_PARENT: i32 = -2;
/// A special value used for internal representation of special case in /// A special value used for internal representation of special case in
/// dirstate v1 format. /// dirstate v1 format.
pub const SIZE_NON_NORMAL: i32 = -1; pub const SIZE_NON_NORMAL: i32 = -1;
impl DirstateEntry { impl DirstateEntry {
pub fn new( pub fn from_v2_data(
wdir_tracked: bool, wdir_tracked: bool,
p1_tracked: bool, p1_tracked: bool,
p2_info: bool, p2_info: bool,
mode_size: Option<(i32, i32)>, mode_size: Option<(i32, i32)>,
mtime: Option<i32>, mtime: Option<i32>,
) -> Self { ) -> Self {
let mut flags = Flags::empty(); let mut flags = Flags::empty();
flags.set(Flags::WDIR_TRACKED, wdir_tracked); flags.set(Flags::WDIR_TRACKED, wdir_tracked);
} }
pub fn any_tracked(&self) -> bool { pub fn any_tracked(&self) -> bool {
self.flags.intersects( self.flags.intersects(
Flags::WDIR_TRACKED | Flags::P1_TRACKED | Flags::P2_INFO, Flags::WDIR_TRACKED | Flags::P1_TRACKED | Flags::P2_INFO,
) )
} }
/// Returns `(wdir_tracked, p1_tracked, p2_info, mode_size, mtime)`
pub(crate) fn v2_data(
&self,
) -> (bool, bool, bool, Option<(i32, i32)>, Option<i32>) {
AlphareUnsubmitted
Not Done

This would probably be more readable with a struct with named field, but it can be done in a follow-up.

Alphare: This would probably be more readable with a struct with named field, but it can be done in a…
if !self.any_tracked() {
// TODO: return an Option instead?
panic!("Accessing v1_state of an untracked DirstateEntry")
}
let wdir_tracked = self.flags.contains(Flags::WDIR_TRACKED);
let p1_tracked = self.flags.contains(Flags::P1_TRACKED);
let p2_info = self.flags.contains(Flags::P2_INFO);
let mode_size = self.mode_size;
let mtime = self.mtime;
(wdir_tracked, p1_tracked, p2_info, mode_size, mtime)
}
fn v1_state(&self) -> EntryState { fn v1_state(&self) -> EntryState {
if !self.any_tracked() { if !self.any_tracked() {
// TODO: return an Option instead? // TODO: return an Option instead?
panic!("Accessing v1_state of an untracked DirstateEntry") panic!("Accessing v1_state of an untracked DirstateEntry")
} }
if self.removed() { if self.removed() {
EntryState::Removed EntryState::Removed
} else if self.merged() { } else if self.merged() {

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

} }
NodeRef::OnDisk(node) => node.entry(), NodeRef::OnDisk(node) => node.entry(),
} }
} }
pub(super) fn state( pub(super) fn state(
&self, &self,
) -> Result<Option<EntryState>, DirstateV2ParseError> { ) -> Result<Option<EntryState>, DirstateV2ParseError> {
match self { Ok(self.entry()?.map(|e| e.state()))
NodeRef::InMemory(_path, node) => {
Ok(node.data.as_entry().map(|entry| entry.state()))
}
NodeRef::OnDisk(node) => node.state(),
}
} }
pub(super) fn cached_directory_mtime( pub(super) fn cached_directory_mtime(
&self, &self,
) -> Option<&'tree on_disk::Timestamp> { ) -> Option<&'tree on_disk::Timestamp> {
match self { match self {
NodeRef::InMemory(_path, node) => match &node.data { NodeRef::InMemory(_path, node) => match &node.data {
NodeData::CachedDirectory { mtime } => Some(mtime), NodeData::CachedDirectory { mtime } => Some(mtime),

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

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;
use crate::utils::hg_path::HgPath; use crate::utils::hg_path::HgPath;
use crate::DirstateEntry; use crate::DirstateEntry;
use crate::DirstateError; use crate::DirstateError;
use crate::DirstateParents; use crate::DirstateParents;
use crate::EntryState; use bitflags::bitflags;
use bytes_cast::unaligned::{I32Be, I64Be, U16Be, U32Be}; use bytes_cast::unaligned::{I32Be, I64Be, U16Be, U32Be};
use bytes_cast::BytesCast; use bytes_cast::BytesCast;
use format_bytes::format_bytes; use format_bytes::format_bytes;
use std::borrow::Cow; use std::borrow::Cow;
use std::convert::{TryFrom, TryInto}; use std::convert::{TryFrom, TryInto};
use std::time::{Duration, SystemTime, UNIX_EPOCH}; use std::time::{Duration, SystemTime, UNIX_EPOCH};
/// Added at the start of `.hg/dirstate` when the "v2" format is used. /// Added at the start of `.hg/dirstate` when the "v2" format is used.
/// In bytes from `self.full_path.start` /// In bytes from `self.full_path.start`
base_name_start: PathSize, base_name_start: PathSize,
copy_source: OptPathSlice, copy_source: OptPathSlice,
children: ChildNodes, children: ChildNodes,
pub(super) descendants_with_entry_count: Size, pub(super) descendants_with_entry_count: Size,
pub(super) tracked_descendants_count: Size, pub(super) tracked_descendants_count: Size,
/// Depending on the value of `state`: /// Depending on the bits in `flags`:
/// ///
/// * A null byte: `data` is not used. /// * If any of `WDIR_TRACKED`, `P1_TRACKED`, or `P2_INFO` are set, the
/// node has an entry.
/// ///
/// * A `n`, `a`, `r`, or `m` ASCII byte: `state` and `data` together /// - If `HAS_MODE_AND_SIZE` is set, `data.mode` and `data.size` are
/// represent a dirstate entry like in the v1 format. /// meaningful. Otherwise they are set to zero
/// - If `HAS_MTIME` is set, `data.mtime` is meaningful. Otherwise it is
/// set to zero.
///
/// * If none of `WDIR_TRACKED`, `P1_TRACKED`, `P2_INFO`, or `HAS_MTIME`
/// are set, the node does not have an entry and `data` is set to all
/// zeros.
///
/// * If none of `WDIR_TRACKED`, `P1_TRACKED`, `P2_INFO` are set, but
/// `HAS_MTIME` is set, the bytes of `data` should instead be
/// interpreted as the `Timestamp` for the mtime of a cached directory.
/// ///
/// * A `d` ASCII byte: the bytes of `data` should instead be interpreted /// The presence of this combination of flags means that at some point,
/// as the `Timestamp` for the mtime of a cached directory. /// this path in the working directory was observed:
///
/// The presence of this state means that at some point, this path in
/// the working directory was observed:
/// ///
/// - To be a directory /// - To be a directory
/// - With the modification time as given by `Timestamp` /// - With the modification time as given by `Timestamp`
/// - 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
/// `TreeMetadata::ignore_patterns_hash`. /// `TreeMetadata::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, flags: Flags,
data: Entry, data: Entry,
} }
#[derive(BytesCast, Copy, Clone)] bitflags! {
#[derive(BytesCast)]
#[repr(C)]
struct Flags: u8 {
const WDIR_TRACKED = 1 << 0;
const P1_TRACKED = 1 << 1;
const P2_INFO = 1 << 2;
const HAS_MODE_AND_SIZE = 1 << 3;
const HAS_MTIME = 1 << 4;
}
}
#[derive(BytesCast, Copy, Clone, Debug)]
#[repr(C)] #[repr(C)]
struct Entry { struct Entry {
mode: I32Be, mode: I32Be,
mtime: I32Be, mtime: I32Be,
size: I32Be, size: I32Be,
} }
/// Duration since the Unix epoch /// Duration since the Unix epoch
) -> Result<Option<&'on_disk HgPath>, DirstateV2ParseError> { ) -> Result<Option<&'on_disk HgPath>, DirstateV2ParseError> {
Ok(if self.has_copy_source() { Ok(if self.has_copy_source() {
Some(read_hg_path(on_disk, self.copy_source)?) Some(read_hg_path(on_disk, self.copy_source)?)
} else { } else {
None None
}) })
} }
fn has_entry(&self) -> bool {
self.flags.intersects(
Flags::WDIR_TRACKED | Flags::P1_TRACKED | Flags::P2_INFO,
)
}
pub(super) fn node_data( pub(super) fn node_data(
&self, &self,
) -> Result<dirstate_map::NodeData, DirstateV2ParseError> { ) -> Result<dirstate_map::NodeData, DirstateV2ParseError> {
let entry = |state| { if self.has_entry() {
dirstate_map::NodeData::Entry(self.entry_with_given_state(state)) Ok(dirstate_map::NodeData::Entry(self.assume_entry()))
}; } else if let Some(&mtime) = self.cached_directory_mtime() {
Ok(dirstate_map::NodeData::CachedDirectory { mtime })
match self.state { } else {
b'\0' => Ok(dirstate_map::NodeData::None), Ok(dirstate_map::NodeData::None)
b'd' => Ok(dirstate_map::NodeData::CachedDirectory {
mtime: *self.data.as_timestamp(),
}),
b'n' => Ok(entry(EntryState::Normal)),
b'a' => Ok(entry(EntryState::Added)),
b'r' => Ok(entry(EntryState::Removed)),
b'm' => Ok(entry(EntryState::Merged)),
_ => Err(DirstateV2ParseError),
} }
} }
pub(super) fn cached_directory_mtime(&self) -> Option<&Timestamp> { pub(super) fn cached_directory_mtime(&self) -> Option<&Timestamp> {
if self.state == b'd' { if self.flags.contains(Flags::HAS_MTIME) && !self.has_entry() {
Some(self.data.as_timestamp()) Some(self.data.as_timestamp())
} else { } else {
None None
} }
} }
pub(super) fn state( fn assume_entry(&self) -> DirstateEntry {
&self, // TODO: convert through raw bits instead?
) -> Result<Option<EntryState>, DirstateV2ParseError> { let wdir_tracked = self.flags.contains(Flags::WDIR_TRACKED);
match self.state { let p1_tracked = self.flags.contains(Flags::P1_TRACKED);
b'\0' | b'd' => Ok(None), let p2_info = self.flags.contains(Flags::P2_INFO);
b'n' => Ok(Some(EntryState::Normal)), let mode_size = if self.flags.contains(Flags::HAS_MODE_AND_SIZE) {
b'a' => Ok(Some(EntryState::Added)), Some((self.data.mode.into(), self.data.size.into()))
b'r' => Ok(Some(EntryState::Removed)), } else {
b'm' => Ok(Some(EntryState::Merged)), None
_ => Err(DirstateV2ParseError), };
} let mtime = if self.flags.contains(Flags::HAS_MTIME) {
} Some(self.data.mtime.into())
} else {
fn entry_with_given_state(&self, state: EntryState) -> DirstateEntry { None
// For now, the on-disk representation of DirstateEntry in dirstate-v2 };
// format is equivalent to that of dirstate-v1. When that changes, add DirstateEntry::from_v2_data(
// a new constructor. wdir_tracked,
DirstateEntry::from_v1_data( p1_tracked,
state, p2_info,
self.data.mode.get(), mode_size,
self.data.size.get(), mtime,
self.data.mtime.get(),
) )
} }
pub(super) fn entry( pub(super) fn entry(
&self, &self,
) -> Result<Option<DirstateEntry>, DirstateV2ParseError> { ) -> Result<Option<DirstateEntry>, DirstateV2ParseError> {
Ok(self if self.has_entry() {
.state()? Ok(Some(self.assume_entry()))
.map(|state| self.entry_with_given_state(state))) } else {
Ok(None)
}
} }
pub(super) fn children<'on_disk>( pub(super) fn children<'on_disk>(
&self, &self,
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
) -> Result<&'on_disk [Node], DirstateV2ParseError> { ) -> Result<&'on_disk [Node], DirstateV2ParseError> {
read_nodes(on_disk, self.children) read_nodes(on_disk, self.children)
} }
.descendants_with_entry_count .descendants_with_entry_count
.get(), .get(),
tracked_descendants_count: self.tracked_descendants_count.get(), tracked_descendants_count: self.tracked_descendants_count.get(),
}) })
} }
} }
impl Entry { impl Entry {
fn from_dirstate_entry(entry: &DirstateEntry) -> (Flags, Self) {
let (wdir_tracked, p1_tracked, p2_info, mode_size_opt, mtime_opt) =
entry.v2_data();
// TODO: convert throug raw flag bits instead?
let mut flags = Flags::empty();
flags.set(Flags::WDIR_TRACKED, wdir_tracked);
flags.set(Flags::P1_TRACKED, p1_tracked);
flags.set(Flags::P2_INFO, p2_info);
let (mode, size, mtime);
if let Some((m, s)) = mode_size_opt {
mode = m;
size = s;
flags.insert(Flags::HAS_MODE_AND_SIZE)
} else {
mode = 0;
size = 0;
}
if let Some(m) = mtime_opt {
mtime = m;
flags.insert(Flags::HAS_MTIME);
} else {
mtime = 0;
}
let raw_entry = Entry {
mode: mode.into(),
size: size.into(),
mtime: mtime.into(),
};
(flags, raw_entry)
}
fn from_timestamp(timestamp: Timestamp) -> Self { fn from_timestamp(timestamp: Timestamp) -> Self {
// Safety: both types implement the `ByteCast` trait, so we could // Safety: both types implement the `ByteCast` trait, so we could
// safely use `as_bytes` and `from_bytes` to do this conversion. Using // safely use `as_bytes` and `from_bytes` to do this conversion. Using
// `transmute` instead makes the compiler check that the two types // `transmute` instead makes the compiler check that the two types
// have the same size, which eliminates the error case of // have the same size, which eliminates the error case of
// `from_bytes`. // `from_bytes`.
unsafe { std::mem::transmute::<Timestamp, Entry>(timestamp) } unsafe { std::mem::transmute::<Timestamp, Entry>(timestamp) }
} }
let (meta, _) = TreeMetadata::from_bytes(metadata) let (meta, _) = TreeMetadata::from_bytes(metadata)
.map_err(|_| DirstateV2ParseError)?; .map_err(|_| DirstateV2ParseError)?;
fn recur<'on_disk>( fn recur<'on_disk>(
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
nodes: ChildNodes, nodes: ChildNodes,
f: &mut impl FnMut(&'on_disk HgPath), f: &mut impl FnMut(&'on_disk HgPath),
) -> Result<(), DirstateV2ParseError> { ) -> Result<(), DirstateV2ParseError> {
for node in read_nodes(on_disk, nodes)? { for node in read_nodes(on_disk, nodes)? {
if let Some(state) = node.state()? { if let Some(entry) = node.entry()? {
if state.is_tracked() { if entry.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, meta.root_nodes, &mut f) recur(on_disk, meta.root_nodes, &mut f)
} else { } else {
PathSlice { PathSlice {
start: 0.into(), start: 0.into(),
len: 0.into(), len: 0.into(),
} }
}; };
on_disk_nodes.push(match node { on_disk_nodes.push(match node {
NodeRef::InMemory(path, node) => { NodeRef::InMemory(path, node) => {
let (state, data) = match &node.data { let (flags, data) = match &node.data {
dirstate_map::NodeData::Entry(entry) => ( dirstate_map::NodeData::Entry(entry) => {
entry.state().into(), Entry::from_dirstate_entry(entry)
Entry { }
mode: entry.mode().into(),
mtime: entry.mtime().into(),
size: entry.size().into(),
},
),
dirstate_map::NodeData::CachedDirectory { mtime } => { dirstate_map::NodeData::CachedDirectory { mtime } => {
(b'd', Entry::from_timestamp(*mtime)) (Flags::HAS_MTIME, Entry::from_timestamp(*mtime))
} }
dirstate_map::NodeData::None => ( dirstate_map::NodeData::None => (
b'\0', Flags::empty(),
Entry { Entry {
mode: 0.into(), mode: 0.into(),
mtime: 0.into(),
size: 0.into(), size: 0.into(),
mtime: 0.into(),
}, },
), ),
}; };
Node { Node {
children, children,
copy_source, copy_source,
full_path, full_path,
base_name_start: u16::try_from(path.base_name_start()) base_name_start: u16::try_from(path.base_name_start())
// Could only panic for paths over 64 KiB // Could only panic for paths over 64 KiB
.expect("dirstate-v2 path length overflow") .expect("dirstate-v2 path length overflow")
.into(), .into(),
descendants_with_entry_count: node descendants_with_entry_count: node
.descendants_with_entry_count .descendants_with_entry_count
.into(), .into(),
tracked_descendants_count: node tracked_descendants_count: node
.tracked_descendants_count .tracked_descendants_count
.into(), .into(),
state, flags,
data, data,
} }
} }
NodeRef::OnDisk(node) => Node { NodeRef::OnDisk(node) => Node {
children, children,
copy_source, copy_source,
full_path, full_path,
..*node ..*node

rust/hg-cpython/src/dirstate/item.rs

if let Some((mode, size, mtime)) = parentfiledata { if let Some((mode, size, mtime)) = parentfiledata {
if has_meaningful_data { if has_meaningful_data {
mode_size_opt = Some((mode, size)) mode_size_opt = Some((mode, size))
} }
if has_meaningful_mtime { if has_meaningful_mtime {
mtime_opt = Some(mtime) mtime_opt = Some(mtime)
} }
} }
let entry = DirstateEntry::new( let entry = DirstateEntry::from_v2_data(
wc_tracked, p1_tracked, p2_info, mode_size_opt, mtime_opt, wc_tracked, p1_tracked, p2_info, mode_size_opt, mtime_opt,
); );
DirstateItem::create_instance(py, Cell::new(entry)) DirstateItem::create_instance(py, Cell::new(entry))
} }
@property @property
def state(&self) -> PyResult<PyBytes> { def state(&self) -> PyResult<PyBytes> {
let state_byte: u8 = self.entry(py).get().state().into(); let state_byte: u8 = self.entry(py).get().state().into();