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
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

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 28383

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
}, },
}) })
} }