~bzr-pqm/bzr/bzr.dev

============================================

Merge Directive format 2 and Bundle format 4

============================================

:Date: 2007-06-21

Motivation

----------

Merge Directive format 2 represents a request to perform a certain merge.  It

provides access to all the data necessary to perform that merge, by including

a branch URL or a bundle payload.  It typically will include a preview of

what applying the patch would do.

Bundle Format 4 is designed to be a compact format for storing revision

metadata that can be generated quickly and installed into a repository

efficiently.  It is not intended to be human-readable.

Note

----

These two formats, taken together, can be viewed as the successor of Bundle

format 0.9, so their specifications are combined.  It is expected that in the

future, bundle and merge-directive formats will vary independently.

Bundle Format Name

------------------

This is the fourth bundle format to see public use.  Previous versions were

0.7, 0.8, and 0.9.  Only 0.7's version number was aligned with a Bazaar

release.

Dependencies

------------

- Container format 1

- Multiparent diffs

- Bencode

- Patch-RIO

Description

-----------

Merge Directives fulfil the role previous bundle formats had of requesting a

merge to be performed, but are a more flexible way of doing so.  With the

introduction of these two formats, there is a clear split between "directive",

which is a request to merge (and therefore signable), and "bundle", which is

just data.

Merge Directive format 2 may provide a patch preview of the change being

requested.  If a preview is supplied, the receiving client will verify that

the actual change matches the preview.

Merge Directive format 2 also includes a testament hash, to ensure that if a

branch is used, the branch cannot be subverted to cause the wrong changes to be

applied.

Bundle format 4 is designed to trade human-readability for speed and

compactness.  It does not contain a human-readable "prelude" patch.

Merge Directive 2 Contents

--------------------------

This format consists of three sections, in the following order.

Patch-RIO command section

~~~~~~~~~~~~~~~~~~~~~~~~~

This section is identical to the corresponding section in Format 1 merge

directives, except as noted below.  It is mandatory.  It is terminated by a

line reading ``#`` that is not preceeded by a line ending with ``\``.

In order to support cherry-picking and patch comparison, this format adds a new

piece of information, the ``base_revision_id``.  This is a suggested base

revision for merging.  It may be supplied by the user.  If not, it is

calculated using the standard merge base algorithm, with the ``revision_id``

and target branch's ``last_revision`` as its inputs.

When merging, clients should use the ``base_revision_id`` when it is not

already present in the ancestry of the ``last_revision`` of the target branch.

If it is already present, clients should calculate a merge base in the normal

way.

Patch preview section

~~~~~~~~~~~~~~~~~~~~~

This section is optional.  It begins with the line ``# Begin patch``.  It is

terminated by the end-of-file or by the beginning of a bundle section.

Its contents are a unified diff, as per the ``bzr diff`` command.  The FROM

revision is the ``base_revision_id`` specified in the Patch-RIO section.

Bundle section

~~~~~~~~~~~~~~

This section is optional, but if it is not supplied, a source_branch must be

supplied.  It begins with the line ``# Begin bundle``, and is terminated by the

end-of-file.

The contents are a base-64 encoded bundle.  This may be any bundle format, but

formats 4+ are strongly recommended.  The base revision is the newest revision

in the source branch which is an ancestor of all revisions not present in

target which are ancestors of revision_id.

This base revision may or may not be the same as the ``base_revision_id``.  In

particular, the ``base_revision_id`` may specify a cherry-pick, but all the

ancestors of the ``base_revision_id`` should be installed in the target

repository before performing such a merge.

Bundle 4 Contents

-----------------

Bazaar revision bundles  begin with a format marker that reads

``# Bazaar revision bundle v4`` in plaintext.  The remainder of the file is a

``Bazaar pack format 1`` container.  The container is compressed using bzip2.

Putting the format marker in plaintext ensures that old clients will give good

diagnostics, but renders the file unreadable by standard bzip2 utilities.

Serialization

~~~~~~~~~~~~~

Format 4 records revision and inventory records in their repository

serialization format.  This minimizes translation and compression costs

in the common case, where the sender and receiver use the same serialization

format for their repository. Steps have been taken to ensure a faithful

conversion when serialization formats are mismatched.

Bundle Records

~~~~~~~~~~~~~~

The bundle format creates a single bundle-level record out of two container

records.  The first container record contains metainfo as a Bencoded dict.  The

second container record contains the body.

The bundle record name is associated with the metainfo record.  The body record

is anonymous.

Record metainfo

~~~~~~~~~~~~~~~

:record_kind: The storage strategy of the record.  May be ``fulltext`` (the

    record body contains the full text of the value), ``mpdiff`` (the record

    body contains a multi-parent diff of the value), or ``header`` (no record

    body).

:parents: Used in fulltext and mpdiff records.  The revisions that should be

    noted as parents of this revision in the repository.  For mpdiffs, this is

    also the list of build-parents.

:sha1: Used in mpdiff records.  The sha-1 hash of the full-text value.

Bundle record naming

~~~~~~~~~~~~~~~~~~~~~

All bundle records have a single name, which is associated with the metainfo

container record.  Records are named according to the body's content-kind,

revision-id, and file-id.

Content-kind may be one of:

:file: a version of a user file

:inventory: the tree inventory

:revision: the revision metadata for a revision

:signature: the revision signature for a revision

Names are constructed like so: ``content-kind/revision-id/file-id``.  Values

are iterpreted left-to-right, so if two values are present, they are

content-kind and revision-id.

A record has a file-id if-and-only-if it is a file record.

Info records have no revision or file-id.

Inventory, revision and signature all have content-kind and revision-id, but

no file-id.

Layout

~~~~~~

The first record is an info/header record.

The subsequent records are mpdiff file records.  The are ordered first by file

id, then in topological order by revision-id.

The next records are mpdiff inventory records.  They are topologically sorted.

The next records are revision and signature fulltexts.  They are interleaved

and topologically sorted.

Info record

~~~~~~~~~~~

The info record has type ``header``.  It has no revision_id or file_id.

Its metadata contains:

:serializer: A string describing the serialization format used for inventory

    and revision data.  May be ``xml5``, ``xml6`` or ``xml7``.

:supports_rich_root: 1 if the source repository supports rich roots,

    0 otherwise.

Implementation notes

~~~~~~~~~~~~~~~~~~~~

- knit deltas contain almost enough information to extract the original

  SequenceMatcher.get_matching_blocks() call used to produce them.  Combining

  that information with the relevant fulltexts allows us to avoid performing

  sequence matching on any fulltexts for which we have deltas.

- MultiParent deltas contain ``get_matching_blocks`` output almost verbatim,

  but if there is more than one parent, the information about the leftmost

  parent may be incomplete.  However, for single-parent multiparent diffs, we

  can extract the ``SequenceMatcher.get_matching_blocks`` output, and therefore

  ``the SequenceMatcher.get_opcodes`` output used to create knit deltas.

Installing data across serialization mismatches

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In practice, there cannot be revision serialization mismatches, because the

serialization of revisions has been consistent in serializations 5-7

If there is a mismatch in inventory serialization formats, the receiver can

  1. extract the inventory objects for the parents

  2. serialize them using the bundle serialize

  3. apply the mpdiff

  4. calculate the fulltext sha1

  5. compare the calculated sha1 to the expected sha1

  6. deserialize using the bundle serializer

  7. serialize using the repository serializer

  8. add to the repository

This is much slower, of course.  But since the since the fulltext is verified

at step 5, it should be just as safe as any other conversion.

Model differences

~~~~~~~~~~~~~~~~~

Note that there may be model differences requiring additional changes.  These

differences are described by the "supports_rich_root" value in the info record.

A subset of xml6 and xml7 records are compatible with xml5 (i.e. those that

were converted from xml5 originally).

When installing from a bundle whose serializer supports tree references to a

repository that does not support tree references, clients should halt if they

encounter a record containing a tree reference.

When installing from a supports_rich_root bundle to a repository that does not

support rich roots, clients should halt if they encounter an inventory record

whose root directory revision-id does not match the inventory revision id.

When installing from a bundle that does not support rich roots to a repository

that does, additional knits should be added for the root directory, with a

revision for each inventory revision.

Validating preview patches

~~~~~~~~~~~~~~~~~~~~~~~~~~

When applying a merge directive that includes a preview, clients should

verify that the preview matches the changes requested by the merge directive.

In order to do this, the client should generate a diff from the

``base_revision_id`` to the ``revision_id``.  This diff should be compared

against the preview patch, making allowances for the fact that whitespace

munging may have occurred.

One form of whitespace munging that has been observed is line-ending

conversion.  Certain mail clients such as Evolution do not respect the

line-endings of text attachments.  Since line-ending conversion is unlikely to

alter the meaning of a patch, it seems safe to ignore line endings when

comparing the preview patch.

Another form of whitespace munging that has been observed is

trailing-whitespace stripping.  Again, it seems unlikely that stripping

trailing whitespace could alter the meaning of a patch.  Such a distinction

is also invisible to readers, so ignoring it does not create a new threat.  So

it seems reasonable to ignore trailing whitespace when comparing the patches.

Other mungings are possible, but it is recommended not to implement support

for them until they have been observed.  Each of these changes makes the

comparison more approximate, and the more approximate it becomes, the easier it

is to provide a preview patch that does not match the requested changes.