( )⚙ D11625 dirstate-v2: Document flags/mode/size/mtime fields of tree nodes

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D11625

dirstate-v2: Document flags/mode/size/mtime fields of tree nodes
ClosedPublic

Authored by SimonSapin on Oct 11 2021, 4:31 PM.

Details

Reviewers
mharbison72
Group Reviewers
hg-reviewers
Commits
rHG77fc340acad7: dirstate-v2: Document flags/mode/size/mtime fields of tree nodes
Summary

This file format modification was previously left incomplete because of
planned upcoming changes. Not all of these changes have been made yet,
but documenting what exists today will help talking more widely about it.

Diff Detail

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

Event Timeline

SimonSapin created this revision.Oct 11 2021, 4:31 PM
mharbison72 added a subscriber: mharbison72.Oct 12 2021, 12:39 AM

This seems fine, but I couldn't import it without the previous commit, and I'd like someone who knows Rust to handle that.

mercurial/helptext/internals/dirstate-v2.txt
405

s/called/call/

424

Are the other bits being masked out? There's a dirstate propose on the wiki to track the u+x bit on filesystems that don't support that, but it required setting and checking a bit for a FIFO or something exotic that Mercurial wouldn't handle anyway. If we're starting fresh, it would be nice to avoid the hack.

SimonSapin added inline comments.Oct 12 2021, 7:14 AM
mercurial/helptext/internals/dirstate-v2.txt
424

At the moment all 32 bits are whatever we got from stat_result.st_mode, same as in dirstate-v1. But the status algorithm only looks at the exec bit.

By the way maybe status should also look at the file type, in case a normal file became a symlink or vice versa. But last I tried I didn’t manage to craft a test case that does this without changing the mtime, since touch -d follows symlinks.

I’m considering removing this mode field in dirstate-v2 and replacing it with a single HAS_EXEC_PERMISSION bit (plus maybe an IS_SYMLINK bit), but that’s not for this patch which document the current format.

SimonSapin updated this revision to Diff 30711.Oct 12 2021, 7:25 AM
SimonSapin updated this revision to Diff 30712.Oct 12 2021, 7:49 AM
SimonSapin added a comment.Oct 12 2021, 7:50 AM

I couldn't import it without the previous commit, and I'd like someone who knows Rust to handle that.

To avoid this review dependency I’ve inverted the order of these two commits. This one now documents the previous format, and the commit that changes the format then also updates the documentation.

mharbison72 accepted this revision.Oct 12 2021, 12:17 PM

LGTM, but I still get an import error for this. Since there are a bunch of accepted things not pushed yet, maybe this has a dependency on one of those things.

$ hg phabimport D11625
applying patch from D11625
patching file rust/hg-core/src/dirstate_tree/on_disk.rs
Hunk #2 FAILED at 93
abort: patch failed to apply
mercurial/helptext/internals/dirstate-v2.txt
424

+1 for doing that before freezing the format. (I think the wiki page also had bits to indicate if each was emulated, but I don't have time to find it now.)

456

/dependening/depending/

This revision is now accepted and ready to land.Oct 12 2021, 12:17 PM
SimonSapin added a comment.Oct 12 2021, 12:46 PM

Is it on top of hg-committed / 38deb65d4441 that this does not apply cleanly? If so this is because because D11623 hasn’t been pushed to hg-commited yet. If you can fix that that should solve this import.

martinvonz edited parent revisions, added: D11623: dirstate-v2: Use "byte sequence" in docs; removed: D11624: dirstate-v2: Change the representation of negative directory mtime.Oct 12 2021, 1:09 PM
martinvonz added a subscriber: martinvonz.

I changed this one's parent to be D11623 since D11624 was abandoned. I hope that's how you meant it to be.

SimonSapin added a comment.Oct 12 2021, 8:20 PM

Yes that’s what I meant. Thanks!

Revision Contents
Changeset List

Diff 30716

mercurial/helptext/internals/dirstate-v2.txt

* Offset 26: * Offset 26:
Number as a 32-bit integer of descendant nodes in this subtree, Number as a 32-bit integer of descendant nodes in this subtree,
not including this node itself, not including this node itself,
that represent files tracked in the working directory. that represent files tracked in the working directory.
(For example, `hg rm` makes a file untracked.) (For example, `hg rm` makes a file untracked.)
This counter is used to implement `has_tracked_dir`. This counter is used to implement `has_tracked_dir`.
* Offset 30 and more: * Offset 30:
**TODO:** docs not written yet Some boolean values packed as bits of a single byte.
as this part of the format might be changing soon. Starting from least-significant, bit masks are::
WDIR_TRACKED = 1 << 0
P1_TRACKED = 1 << 1
P2_INFO = 1 << 2
HAS_MODE_AND_SIZE = 1 << 3
HAS_MTIME = 1 << 4
Other bits are unset. The meaning of these bits are:
`WDIR_TRACKED`
Set if the working directory contains a tracked file at this node’s path.
This is typically set and unset by `hg add` and `hg rm`.
`P1_TRACKED`
set if the working directory’s first parent changeset
(whose node identifier is found in tree metadata)
contains a tracked file at this node’s path.
This is a cache to reduce manifest lookups.
`P2_INFO`
Set if the file has been involved in some merge operation.
Either because it was actually merged,
or because the version in the second parent p2 version was ahead,
or because some rename moved it there.
In either case `hg status` will want it displayed as modified.
Files that would be mentioned at all in the `dirstate-v1` file format
have a node with at least one of the above three bits set in `dirstate-v2`.
Let’s call these files "tracked anywhere",
mharbison72Unsubmitted
Not Done

s/called/call/

mharbison72: s/called/call/
and "untracked" the nodes with all three of these bits unset.
Untracked nodes are typically for directories:
they hold child nodes and form the tree structure.
Additional untracked nodes may also exist.
Although implementations should strive to clean up nodes
that are entirely unused, other untracked nodes may also exist.
For example, a future version of Mercurial might in some cases
add nodes for untracked files or/and ignored files in the working directory
in order to optimize `hg status`
by enabling it to skip `readdir` in more cases.
When a node is for a file tracked anywhere,
the rest of the node data is three fields:
* Offset 31:
If `HAS_MODE_AND_SIZE` is unset, four zero bytes.
Otherwise, a 32-bit integer for the Unix mode (as in `stat_result.st_mode`)
expected for this file to be considered clean.
Only the `S_IXUSR` bit (owner has execute permission) is considered.
mharbison72Unsubmitted
Not Done

Are the other bits being masked out? There's a dirstate propose on the wiki to track the u+x bit on filesystems that don't support that, but it required setting and checking a bit for a FIFO or something exotic that Mercurial wouldn't handle anyway. If we're starting fresh, it would be nice to avoid the hack.

mharbison72: Are the other bits being masked out? There's a dirstate propose on the wiki to track the u+x…
SimonSapinAuthorUnsubmitted
Done

At the moment all 32 bits are whatever we got from stat_result.st_mode, same as in dirstate-v1. But the status algorithm only looks at the exec bit.

By the way maybe status should also look at the file type, in case a normal file became a symlink or vice versa. But last I tried I didn’t manage to craft a test case that does this without changing the mtime, since touch -d follows symlinks.

I’m considering removing this mode field in dirstate-v2 and replacing it with a single HAS_EXEC_PERMISSION bit (plus maybe an IS_SYMLINK bit), but that’s not for this patch which document the current format.

SimonSapin: At the moment all 32 bits are whatever we got from `stat_result.st_mode`, same as in dirstate…
mharbison72Unsubmitted
Not Done

+1 for doing that before freezing the format. (I think the wiki page also had bits to indicate if each was emulated, but I don't have time to find it now.)

mharbison72: +1 for doing that before freezing the format. (I think the wiki page also had bits to indicate…
* Offset 35:
If `HAS_MTIME` is unset, four zero bytes.
Otherwise, a 32-bit integer for expected modified time of the file
(as in `stat_result.st_mtime`),
truncated to its 31 least-significant bits.
Unlike in dirstate-v1, negative values are not used.
* Offset 39:
If `HAS_MODE_AND_SIZE` is unset, four zero bytes.
Otherwise, a 32-bit integer for expected size of the file
truncated to its 31 least-significant bits.
Unlike in dirstate-v1, negative values are not used.
If an untracked node `HAS_MTIME` *unset*, this space is unused:
* Offset 31:
12 bytes set to zero
If an untracked node `HAS_MTIME` *set*,
what follows is the modification time of a directory
represented with separated second and sub-second components
since the Unix epoch:
* Offset 31:
The number of seconds as a signed (two’s complement) 64-bit integer.
* Offset 39:
The number of nanoseconds as 32-bit integer.
Always greater than or equal to zero, and strictly less than a billion.
Increasing this component makes the modification time
go forward or backward in time dependening
mharbison72Unsubmitted
Not Done

/dependening/depending/

mharbison72: /dependening/depending/
on the sign of the integral seconds components.
(Note: this is buggy because there is no negative zero integer,
but will be changed soon.)
The presence of a directory modification time means that at some point,
this path in the working directory was observed:
- To be a directory
- With the given modification time
- That time was already strictly in the past when observed,
meaning that later changes cannot happen in the same clock tick
and must cause a different modification time
(unless the system clock jumps back and we get unlucky,
which is not impossible but deemed unlikely enough).
- All direct children of this directory
(as returned by `std::fs::read_dir`)
either have a corresponding dirstate node,
or are ignored by ignore patterns whose hash is in tree metadata.
This means that if `std::fs::symlink_metadata` later reports
the same modification time
and ignored patterns haven’t changed,
a run of status that is not listing ignored files
can skip calling `std::fs::read_dir` again for this directory,
and iterate child dirstate nodes instead.
* (Offset 43: end of this node)

mercurial/pure/parsers.py

It hold multiple attributes It hold multiple attributes
# about file tracking # about file tracking
- wc_tracked: is the file tracked by the working copy - wc_tracked: is the file tracked by the working copy
- p1_tracked: is the file tracked in working copy first parent - p1_tracked: is the file tracked in working copy first parent
- p2_info: the file has been involved in some merge operation. Either - p2_info: the file has been involved in some merge operation. Either
because it was actually merged, or because the p2 version was because it was actually merged, or because the p2 version was
ahead, or because some renamed moved it there. In either case ahead, or because some rename moved it there. In either case
`hg status` will want it displayed as modified. `hg status` will want it displayed as modified.
# about the file state expected from p1 manifest: # about the file state expected from p1 manifest:
- mode: the file mode in p1 - mode: the file mode in p1
- size: the file size in p1 - size: the file size in p1
These value can be set to None, which mean we don't have a meaningful value These value can be set to None, which mean we don't have a meaningful value
to compare with. Either because we don't really care about them as there to compare with. Either because we don't really care about them as there

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

uuid_size: u8, uuid_size: u8,
} }
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],
} }
/// Fields are documented in the *Tree metadata in the docket file*
/// section of `mercurial/helptext/internals/dirstate-v2.txt`
#[derive(BytesCast)] #[derive(BytesCast)]
#[repr(C)] #[repr(C)]
struct TreeMetadata { struct TreeMetadata {
root_nodes: 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,
/// How many bytes of this data file are not used anymore
unreachable_bytes: Size, unreachable_bytes: Size,
/// Current version always sets these bytes to zero when creating or
/// updating a dirstate. Future versions could assign some bits to signal
/// for example "the version that last wrote/updated this dirstate did so
/// in such and such way that can be relied on by versions that know to."
unused: [u8; 4], unused: [u8; 4],
/// If non-zero, a hash of ignore files that were used for some previous /// See *Optional hash of ignore patterns* section of
/// run of the `status` algorithm. /// `mercurial/helptext/internals/dirstate-v2.txt`
///
/// We define:
///
/// * "Root" ignore files are `.hgignore` at the root of the repository if
/// it exists, and files from `ui.ignore.*` config. This set of files is
/// then sorted by the string representation of their path.
/// * The "expanded contents" of an ignore files is the byte string made
/// by concatenating its contents with the "expanded contents" of other
/// files included with `include:` or `subinclude:` files, in inclusion
/// order. This definition is recursive, as included files can
/// themselves include more files.
///
/// This hash is defined as the SHA-1 of the concatenation (in sorted
/// order) of the "expanded contents" of each "root" ignore file.
/// (Note that computing this does not require actually concatenating byte
/// strings into contiguous memory, instead SHA-1 hashing can be done
/// incrementally.)
ignore_patterns_hash: IgnorePatternsHash, ignore_patterns_hash: IgnorePatternsHash,
} }
/// Fields are documented in the *The data file format*
/// section of `mercurial/helptext/internals/dirstate-v2.txt`
#[derive(BytesCast)] #[derive(BytesCast)]
#[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: 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 bits in `flags`:
///
/// * If any of `WDIR_TRACKED`, `P1_TRACKED`, or `P2_INFO` are set, the
/// node has an entry.
///
/// - If `HAS_MODE_AND_SIZE` is set, `data.mode` and `data.size` are
/// 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.
///
/// The presence of this combination of flags means that at some point,
/// this path in the working directory was observed:
///
/// - To be a directory
/// - With the modification time as given by `Timestamp`
/// - That timestamp was already strictly in the past when observed,
/// meaning that later changes cannot happen in the same clock tick
/// and must cause a different modification time (unless the system
/// clock jumps back and we get unlucky, which is not impossible but
/// but deemed unlikely enough).
/// - All direct children of this directory (as returned by
/// `std::fs::read_dir`) either have a corresponding dirstate node, or
/// are ignored by ignore patterns whose hash is in
/// `TreeMetadata::ignore_patterns_hash`.
///
/// This means that if `std::fs::symlink_metadata` later reports the
/// same modification time and ignored patterns haven’t changed, a run
/// of status that is not listing ignored files can skip calling
/// `std::fs::read_dir` again for this directory, iterate child
/// dirstate nodes instead.
flags: Flags, flags: Flags,
data: Entry, data: Entry,
} }
bitflags! { bitflags! {
#[derive(BytesCast)] #[derive(BytesCast)]
#[repr(C)] #[repr(C)]
struct Flags: u8 { struct Flags: u8 {