This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10825

dirstate-v2: Allow tree nodes without an entry to store a timestamp
ClosedPublic

Authored by SimonSapin on Jun 1 2021, 12:50 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGa4de570e61fa: dirstate-v2: Allow tree nodes without an entry to store a timestamp
Summary

Timestamps are stored on 96 bits:

  • 64 bits for the signed number of seconds since the Unix epoch
  • 32 bits for the nanoseconds in the 0 <= ns < 1_000_000_000 range

For now timestamps are not used or set yet.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

SimonSapin created this revision.Jun 1 2021, 12:50 PM
SimonSapin added a commit: rHGa4de570e61fa: dirstate-v2: Allow tree nodes without an entry to store a timestamp.Jun 1 2021, 3:35 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGa4de570e61fa: dirstate-v2: Allow tree nodes without an entry to store a timestamp (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.
baymax updated this revision to Diff 28383.Jun 1 2021, 5:05 PM

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

Revision Contents
Changeset List

Diff 28358

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

match self { match self {
NodeRef::InMemory(_path, node) => { NodeRef::InMemory(_path, node) => {
Ok(node.copy_source.as_ref().map(|s| &**s)) Ok(node.copy_source.as_ref().map(|s| &**s))
} }
NodeRef::OnDisk(node) => node.copy_source(on_disk), NodeRef::OnDisk(node) => node.copy_source(on_disk),
} }
} }
pub(super) fn has_entry(&self) -> bool {
match self {
NodeRef::InMemory(_path, node) => node.entry.is_some(),
NodeRef::OnDisk(node) => node.has_entry(),
}
}
pub(super) fn entry( pub(super) fn entry(
&self, &self,
) -> Result<Option<DirstateEntry>, DirstateV2ParseError> { ) -> Result<Option<DirstateEntry>, DirstateV2ParseError> {
match self { match self {
NodeRef::InMemory(_path, node) => Ok(node.entry), NodeRef::InMemory(_path, node) => {
Ok(node.data.as_entry().copied())
}
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 { match self {
NodeRef::InMemory(_path, node) => { NodeRef::InMemory(_path, node) => {
Ok(node.entry.as_ref().map(|entry| entry.state)) Ok(node.data.as_entry().map(|entry| entry.state))
} }
NodeRef::OnDisk(node) => node.state(), NodeRef::OnDisk(node) => node.state(),
} }
} }
pub(super) fn tracked_descendants_count(&self) -> u32 { pub(super) fn tracked_descendants_count(&self) -> u32 {
match self { match self {
NodeRef::InMemory(_path, node) => node.tracked_descendants_count, NodeRef::InMemory(_path, node) => node.tracked_descendants_count,
NodeRef::OnDisk(node) => node.tracked_descendants_count.get(), NodeRef::OnDisk(node) => node.tracked_descendants_count.get(),
} }
} }
} }
/// Represents a file or a directory /// Represents a file or a directory
#[derive(Default)] #[derive(Default)]
pub(super) struct Node<'on_disk> { pub(super) struct Node<'on_disk> {
/// `None` for directories pub(super) data: NodeData,
pub(super) entry: Option<DirstateEntry>,
pub(super) copy_source: Option<Cow<'on_disk, HgPath>>, pub(super) copy_source: Option<Cow<'on_disk, HgPath>>,
pub(super) children: ChildNodes<'on_disk>, pub(super) children: ChildNodes<'on_disk>,
/// How many (non-inclusive) descendants of this node are tracked files /// How many (non-inclusive) descendants of this node are tracked files
pub(super) tracked_descendants_count: u32, pub(super) tracked_descendants_count: u32,
} }
pub(super) enum NodeData {
Entry(DirstateEntry),
CachedDirectory { mtime: on_disk::Timestamp },
None,
}
impl Default for NodeData {
fn default() -> Self {
NodeData::None
}
}
impl NodeData {
fn has_entry(&self) -> bool {
match self {
NodeData::Entry(_) => true,
_ => false,
}
}
fn as_entry(&self) -> Option<&DirstateEntry> {
match self {
NodeData::Entry(entry) => Some(entry),
_ => None,
}
}
}
impl<'on_disk> DirstateMap<'on_disk> { impl<'on_disk> DirstateMap<'on_disk> {
pub(super) fn empty(on_disk: &'on_disk [u8]) -> Self { pub(super) fn empty(on_disk: &'on_disk [u8]) -> Self {
Self { Self {
on_disk, on_disk,
root: ChildNodes::default(), root: ChildNodes::default(),
nodes_with_entry_count: 0, nodes_with_entry_count: 0,
nodes_with_copy_source_count: 0, nodes_with_copy_source_count: 0,
} }
WithBasename::to_cow_borrowed, WithBasename::to_cow_borrowed,
|ancestor| { |ancestor| {
if tracked { if tracked {
ancestor.tracked_descendants_count += 1 ancestor.tracked_descendants_count += 1
} }
}, },
)?; )?;
assert!( assert!(
node.entry.is_none(), !node.data.has_entry(),
"duplicate dirstate entry in read" "duplicate dirstate entry in read"
); );
assert!( assert!(
node.copy_source.is_none(), node.copy_source.is_none(),
"duplicate dirstate entry in read" "duplicate dirstate entry in read"
); );
node.entry = Some(*entry); node.data = NodeData::Entry(*entry);
node.copy_source = copy_source.map(Cow::Borrowed); node.copy_source = copy_source.map(Cow::Borrowed);
map.nodes_with_entry_count += 1; map.nodes_with_entry_count += 1;
if copy_source.is_some() { if copy_source.is_some() {
map.nodes_with_copy_source_count += 1 map.nodes_with_copy_source_count += 1
} }
Ok(()) Ok(())
}, },
)?; )?;
// through zero // through zero
match tracked_count_increment { match tracked_count_increment {
1 => ancestor.tracked_descendants_count += 1, 1 => ancestor.tracked_descendants_count += 1,
-1 => ancestor.tracked_descendants_count -= 1, -1 => ancestor.tracked_descendants_count -= 1,
_ => {} _ => {}
} }
}, },
)?; )?;
if node.entry.is_none() { if !node.data.has_entry() {
self.nodes_with_entry_count += 1 self.nodes_with_entry_count += 1
} }
node.entry = Some(new_entry); node.data = NodeData::Entry(new_entry);
Ok(()) Ok(())
} }
fn iter_nodes<'tree>( fn iter_nodes<'tree>(
&'tree self, &'tree self,
) -> impl Iterator< ) -> impl Iterator<
Item = Result<NodeRef<'tree, 'on_disk>, DirstateV2ParseError>, Item = Result<NodeRef<'tree, 'on_disk>, DirstateV2ParseError>,
> + 'tree { > + 'tree {
paths: &[impl AsRef<HgPath>], paths: &[impl AsRef<HgPath>],
) -> Result<(), DirstateV2ParseError> { ) -> Result<(), DirstateV2ParseError> {
for path in paths { for path in paths {
if let Some(node) = Self::get_node_mut( if let Some(node) = Self::get_node_mut(
self.on_disk, self.on_disk,
&mut self.root, &mut self.root,
path.as_ref(), path.as_ref(),
)? { )? {
if let Some(entry) = node.entry.as_mut() { if let NodeData::Entry(entry) = &mut node.data {
entry.clear_mtime(); entry.clear_mtime();
} }
} }
} }
Ok(()) Ok(())
} }
/// Return a faillilble iterator of full paths of nodes that have an /// Return a faillilble iterator of full paths of nodes that have an
dropped = d; dropped = d;
if dropped.was_tracked { if dropped.was_tracked {
node.tracked_descendants_count -= 1; node.tracked_descendants_count -= 1;
} }
} else { } else {
return Ok(None); return Ok(None);
} }
} else { } else {
let had_entry = node.data.has_entry();
if had_entry {
node.data = NodeData::None
}
dropped = Dropped { dropped = Dropped {
was_tracked: node was_tracked: node
.entry .data
.as_ref() .as_entry()
.map_or(false, |entry| entry.state.is_tracked()), .map_or(false, |entry| entry.state.is_tracked()),
had_entry: node.entry.take().is_some(), had_entry,
had_copy_source: node.copy_source.take().is_some(), had_copy_source: node.copy_source.take().is_some(),
}; };
} }
// After recursion, for both leaf (rest_of_path is None) nodes and // After recursion, for both leaf (rest_of_path is None) nodes and
// parent nodes, remove a node if it just became empty. // parent nodes, remove a node if it just became empty.
if node.entry.is_none() if !node.data.has_entry()
&& node.copy_source.is_none() && node.copy_source.is_none()
&& node.children.is_empty() && node.children.is_empty()
{ {
nodes.make_mut(on_disk)?.remove(first_path_component); nodes.make_mut(on_disk)?.remove(first_path_component);
} }
Ok(Some(dropped)) Ok(Some(dropped))
} }
&mut self, &mut self,
filenames: Vec<HgPathBuf>, filenames: Vec<HgPathBuf>,
now: i32, now: i32,
) -> Result<(), DirstateV2ParseError> { ) -> Result<(), DirstateV2ParseError> {
for filename in filenames { for filename in filenames {
if let Some(node) = if let Some(node) =
Self::get_node_mut(self.on_disk, &mut self.root, &filename)? Self::get_node_mut(self.on_disk, &mut self.root, &filename)?
{ {
if let Some(entry) = node.entry.as_mut() { if let NodeData::Entry(entry) = &mut node.data {
entry.clear_ambiguous_mtime(now); entry.clear_ambiguous_mtime(now);
} }
} }
} }
Ok(()) Ok(())
} }
fn non_normal_entries_contains( fn non_normal_entries_contains(
fn has_tracked_dir( fn has_tracked_dir(
&mut self, &mut self,
directory: &HgPath, directory: &HgPath,
) -> Result<bool, DirstateError> { ) -> Result<bool, DirstateError> {
if let Some(node) = self.get_node(directory)? { if let Some(node) = self.get_node(directory)? {
// A node without a `DirstateEntry` was created to hold child // A node without a `DirstateEntry` was created to hold child
// nodes, and is therefore a directory. // nodes, and is therefore a directory.
Ok(!node.has_entry() && node.tracked_descendants_count() > 0) let state = node.state()?;
Ok(state.is_none() && node.tracked_descendants_count() > 0)
} else { } else {
Ok(false) Ok(false)
} }
} }
fn has_dir(&mut self, directory: &HgPath) -> Result<bool, DirstateError> { fn has_dir(&mut self, directory: &HgPath) -> Result<bool, DirstateError> {
if let Some(node) = self.get_node(directory)? { if let Some(node) = self.get_node(directory)? {
// A node without a `DirstateEntry` was created to hold child // A node without a `DirstateEntry` was created to hold child
// nodes, and is therefore a directory. // nodes, and is therefore a directory.
Ok(!node.has_entry()) Ok(node.state()?.is_none())
} else { } else {
Ok(false) Ok(false)
} }
} }
#[timed] #[timed]
fn pack_v1( fn pack_v1(
&mut self, &mut self,

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 crate::EntryState;
use bytes_cast::unaligned::{I32Be, U32Be, U64Be}; use bytes_cast::unaligned::{I32Be, I64Be, U32Be, U64Be};
use bytes_cast::BytesCast; use bytes_cast::BytesCast;
use std::borrow::Cow; use std::borrow::Cow;
use std::convert::{TryFrom, TryInto}; use std::convert::TryFrom;
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.
/// This a redundant sanity check more than an actual "magic number" since /// This a redundant sanity check more than an actual "magic number" since
/// `.hg/requires` already governs which format should be used. /// `.hg/requires` already governs which format should be used.
pub const V2_FORMAT_MARKER: &[u8; 12] = b"dirstate-v2\n"; pub const V2_FORMAT_MARKER: &[u8; 12] = b"dirstate-v2\n";
#[derive(BytesCast)] #[derive(BytesCast)]
#[repr(C)] #[repr(C)]
#[repr(C)] #[repr(C)]
pub(super) struct Node { pub(super) struct Node {
full_path: PathSlice, full_path: PathSlice,
/// In bytes from `self.full_path.start` /// In bytes from `self.full_path.start`
base_name_start: Size, base_name_start: Size,
copy_source: OptPathSlice, copy_source: OptPathSlice,
entry: OptEntry,
children: ChildNodes, children: ChildNodes,
pub(super) tracked_descendants_count: Size, pub(super) tracked_descendants_count: Size,
/// Dependending on the value of `state`:
///
/// * A null byte: `data` represents nothing
/// * A `n`, `a`, `r`, or `m` ASCII byte: `state` and `data` together
/// represents a dirstate entry like in the v1 format.
/// * A `d` ASCII byte: the bytes of `data` should instead be interpreted
/// as the `Timestamp` for the mtime of a cached directory.
///
/// TODO: document directory caching
state: u8,
data: Entry,
} }
/// Either nothing if `state == b'\0'`, or a dirstate entry like in the v1
/// format
#[derive(BytesCast, Copy, Clone)] #[derive(BytesCast, Copy, Clone)]
#[repr(C)] #[repr(C)]
struct OptEntry { struct Entry {
state: u8,
mode: I32Be, mode: I32Be,
mtime: I32Be, mtime: I32Be,
size: I32Be, size: I32Be,
} }
/// Duration since the Unix epoch
#[derive(BytesCast, Copy, Clone)]
#[repr(C)]
pub(super) struct Timestamp {
seconds: I64Be,
/// In `0 .. 1_000_000_000`.
///
/// This timestamp is later or earlier than `(seconds, 0)` by this many
/// nanoseconds, if `seconds` is non-negative or negative, respectively.
nanoseconds: U32Be,
}
/// Counted in bytes from the start of the file /// Counted in bytes from the start of the file
/// ///
/// NOTE: If we decide to never support `.hg/dirstate` files larger than 4 GiB /// NOTE: If we decide to never support `.hg/dirstate` files larger than 4 GiB
/// we could save space by using `U32Be` instead. /// we could save space by using `U32Be` instead.
type Offset = U64Be; type Offset = U64Be;
/// Counted in number of items /// Counted in number of items
/// ///
) -> 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
}) })
} }
pub(super) fn has_entry(&self) -> bool { pub(super) fn node_data(
self.entry.state != b'\0' &self,
) -> Result<dirstate_map::NodeData, DirstateV2ParseError> {
let entry = |state| {
dirstate_map::NodeData::Entry(self.entry_with_given_state(state))
};
match self.state {
b'\0' => 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 state( pub(super) fn state(
&self, &self,
) -> Result<Option<EntryState>, DirstateV2ParseError> { ) -> Result<Option<EntryState>, DirstateV2ParseError> {
Ok(if self.has_entry() { match self.state {
Some( b'\0' | b'd' => Ok(None),
self.entry b'n' => Ok(Some(EntryState::Normal)),
.state b'a' => Ok(Some(EntryState::Added)),
.try_into() b'r' => Ok(Some(EntryState::Removed)),
.map_err(|_| DirstateV2ParseError)?, b'm' => Ok(Some(EntryState::Merged)),
) _ => Err(DirstateV2ParseError),
} else { }
None }
})
fn entry_with_given_state(&self, state: EntryState) -> DirstateEntry {
DirstateEntry {
state,
mode: self.data.mode.get(),
mtime: self.data.mtime.get(),
size: self.data.size.get(),
}
} }
pub(super) fn entry( pub(super) fn entry(
&self, &self,
) -> Result<Option<DirstateEntry>, DirstateV2ParseError> { ) -> Result<Option<DirstateEntry>, DirstateV2ParseError> {
Ok(self.state()?.map(|state| DirstateEntry { Ok(self
state, .state()?
mode: self.entry.mode.get(), .map(|state| self.entry_with_given_state(state)))
mtime: self.entry.mtime.get(),
size: self.entry.size.get(),
}))
} }
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_slice::<Node>(on_disk, self.children) read_slice::<Node>(on_disk, self.children)
} }
pub(super) fn to_in_memory_node<'on_disk>( pub(super) fn to_in_memory_node<'on_disk>(
&self, &self,
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
) -> Result<dirstate_map::Node<'on_disk>, DirstateV2ParseError> { ) -> Result<dirstate_map::Node<'on_disk>, DirstateV2ParseError> {
Ok(dirstate_map::Node { Ok(dirstate_map::Node {
children: dirstate_map::ChildNodes::OnDisk( children: dirstate_map::ChildNodes::OnDisk(
self.children(on_disk)?, self.children(on_disk)?,
), ),
copy_source: self.copy_source(on_disk)?.map(Cow::Borrowed), copy_source: self.copy_source(on_disk)?.map(Cow::Borrowed),
entry: self.entry()?, data: self.node_data()?,
tracked_descendants_count: self.tracked_descendants_count.get(), tracked_descendants_count: self.tracked_descendants_count.get(),
}) })
} }
} }
impl Entry {
fn from_timestamp(timestamp: Timestamp) -> Self {
// Safety: both types implement the `ByteCast` trait, so we could
// safely use `as_bytes` and `from_bytes` to do this conversion. Using
// `transmute` instead makes the compiler check that the two types
// have the same size, which eliminates the error case of
// `from_bytes`.
unsafe { std::mem::transmute::<Timestamp, Entry>(timestamp) }
}
fn as_timestamp(&self) -> &Timestamp {
// Safety: same as above in `from_timestamp`
unsafe { &*(self as *const Entry as *const Timestamp) }
}
}
impl From<&'_ SystemTime> for Timestamp {
fn from(system_time: &'_ SystemTime) -> Self {
let (secs, nanos) = match system_time.duration_since(UNIX_EPOCH) {
Ok(duration) => {
(duration.as_secs() as i64, duration.subsec_nanos())
}
Err(error) => {
let negative = error.duration();
(-(negative.as_secs() as i64), negative.subsec_nanos())
}
};
Timestamp {
seconds: secs.into(),
nanoseconds: nanos.into(),
}
}
}
impl From<&'_ Timestamp> for SystemTime {
fn from(timestamp: &'_ Timestamp) -> Self {
let secs = timestamp.seconds.get();
let nanos = timestamp.nanoseconds.get();
if secs >= 0 {
UNIX_EPOCH + Duration::new(secs as u64, nanos)
} else {
UNIX_EPOCH - Duration::new((-secs) as u64, nanos)
}
}
}
fn read_hg_path( fn read_hg_path(
on_disk: &[u8], on_disk: &[u8],
slice: Slice, slice: Slice,
) -> Result<&HgPath, DirstateV2ParseError> { ) -> Result<&HgPath, DirstateV2ParseError> {
let bytes = read_slice::<u8>(on_disk, slice)?; let bytes = read_slice::<u8>(on_disk, slice)?;
Ok(HgPath::new(bytes)) Ok(HgPath::new(bytes))
} }
write_slice::<u8>(source.as_bytes(), out) write_slice::<u8>(source.as_bytes(), out)
} else { } else {
Slice { Slice {
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) => Node { NodeRef::InMemory(path, node) => {
let (state, data) = match &node.data {
dirstate_map::NodeData::Entry(entry) => (
entry.state.into(),
Entry {
mode: entry.mode.into(),
mtime: entry.mtime.into(),
size: entry.size.into(),
},
),
dirstate_map::NodeData::CachedDirectory { mtime } => {
(b'd', Entry::from_timestamp(*mtime))
}
dirstate_map::NodeData::None => (
b'\0',
Entry {
mode: 0.into(),
mtime: 0.into(),
size: 0.into(),
},
),
};
Node {
children, children,
copy_source, copy_source,
full_path, full_path,
base_name_start: u32::try_from(path.base_name_start()) base_name_start: u32::try_from(path.base_name_start())
// Could only panic for paths over 4 GiB // Could only panic for paths over 4 GiB
.expect("dirstate-v2 offset overflow") .expect("dirstate-v2 offset overflow")
.into(), .into(),
tracked_descendants_count: node tracked_descendants_count: node
.tracked_descendants_count .tracked_descendants_count
.into(), .into(),
entry: if let Some(entry) = &node.entry { state,
OptEntry { data,
state: entry.state.into(),
mode: entry.mode.into(),
mtime: entry.mtime.into(),
size: entry.size.into(),
} }
} else {
OptEntry {
state: b'\0',
mode: 0.into(),
mtime: 0.into(),
size: 0.into(),
} }
},
},
NodeRef::OnDisk(node) => Node { NodeRef::OnDisk(node) => Node {
children, children,
copy_source, copy_source,
full_path, full_path,
..*node ..*node
}, },
}) })
} }