Implementation Details about Changesets Evolution

This page is intended for developer

For a user perspective have a look at the ChangesetEvolution page.

1. Obsstore Format

Markers are stored in an append-only file stored in '.hg/store/obsstore'.

1.1. V1 (current) Format

(see in line document for latest data)

1.1.1. quick summary

• <number-of-successors(=N)><metadata-lenght(=M)><bits-field><precursor>(<successor>*N)<metadata>

• B, I, B, 20s, (20s*N), s*M

1.1.2. longer explanation

The file starts with a version header:

• 1 unsigned byte: version number, starting at zero.

The header is followed by the markers. Each marker is made of:

• 1 unsigned byte: number of new changesets "N", can be zero.
• 1 unsigned 32-bits integer: metadata size "M" in bytes.
• 1 byte: a bit field. It is reserved for flags used in common
  • obsolete marker operations, to avoid repeated decoding of metadata entries.
• 20 bytes: obsoleted changeset identifier.
• N*20 bytes: new changesets identifiers.
• M bytes: metadata as a sequence of nul-terminated strings. Each
  • string contains a key and a value, separated by a colon ':', without additional encoding. Keys cannot contain '\0' or ':' and values cannot contain '\0'.

1.2. V2 (current) Format

1.2.1. motivation

There is two extra information we would like to see in a second version of the format:

• date: There is currently *always* a date in the meta data. So storing it explicitly would be more space efficient. It would also open the way to quickly access the date for sorting purpose (no use case yet but not crazy to think about it)
• parents: When a changesets is pruned (obsoleted, no successors) we needs to records its parents. This is necessary to link the markers chain to the push/pull operation it is relevant to.
• We may want to extend the bit field to 2 bytes. We currently use 1 and can see use case for 3-5 others (tracking the type of changes introduce by the rewriting (desc, patches, content, etc) so we are running short

1.2.2. possible change

Date:

• The date will be a 64bits integer (for seconds since epoch) followed by a 16 bits integer (time zone)
• It will make sense to put the date in front of the markers. that would give markers sorting some semantic.

Parents:

We have multiple option for storing parents:

1. Having an explicite field similar to successors (one byte to know how many parents, then parents)
2. Having an explicite field but store the number of parent in the bit fields (since we never have more than 2 parents)
3. Using the successors field. Having negative number of successors mean it is a prune.

Option (3) is the most space saving but prevent use to store parent information for more changesets if needed in the future (We do not have a final exchange plan yet).

Option (1) and (2) takes 2 to 8 bits more than (3) but are more flexible.

bit field

If we extend the bit field to 2 Bytes, it makes sense to use option (2) for storing parent.

1.2.3. Proposed Format

• <date><timezone><number-of-successors(=N)><metadata-lenght(=M)><bits-field+nb-parents(=P)><precursor>(<successor>*N)(<parents>*P)<metadata>

• L, h, B, I, H, 20s, (20s*N), (20s*P), s*M

The P number would be hidden in the bit field. We need to store 4 possible values here: 0 parents, 1 parent, 2 parents, ø parents information stored. Possible assignement is 00, 01, 10, 11. this let both 0 parent and ø parent info to be 0 module 3.