1.1.5.1   Library changes

These changes will change bzrlib’s API but will not affect the disk format and thus do not pose a significant migration issue.

• For our 20 core use cases, we plan to add targeted API’s to bzrlib that are repository-representation agnostic. These will instead reflect the shape of data access most optimal for that case.
• Deprecate ‘versioned files’ as a library concept. Instead of asking for information about a file-over-time as a special case, we will move to an API that assumes less coupling between the historical information and the ability to obtain texts/deltas etc. Specifically, we need to remove all API’s that act in terms of on disk representation except those within a given repository implementation.
• Create a validator for revisions that is more amenable to use by other parts of the code base than just the gpg signing facility. This can be done today without changing disk, possibly with a performance hit until the disk formats match the validatory logic. It will be hard to tell if we have the right routine for that until all the disk changes are complete, so while this is a library only change, its likely one that will be delayed to near the end of the process.
• Add an explicit API for managing cached annotations. While annotations are considered a cache this is not exposed in such a way that cache operations like ‘drop the cache’ can be performed. On current disk formats the cache is mandatory, but an API to manage would allow refreshing of the cache (e.g. after ghosts are filled in during baz conversions).
• Use the _iter_changes API to perform merges. This is a small change that may remove the need to use inventories in merge, making a dramatic difference to merge performance once the tree shape comparison optimisations are implemented.
• Create a network-efficient revision graph API. This is the logic at the start of push and pull operations, which currently scales O(graph size). Fixing the scaling can be done, but there are tradeoffs to latency and performance to consider, making it a little tricky to get right.
• Working tree disk operation ordering. We plan to change the order in which some operations are done (specifically TreeTransform ones) to improve performance. There is already a 66% performance boost in that area going through review.
• Stop requiring full memory copies of files. Currently bzr requires that it can hold 3 copies of any file its versioning in memory. Solving this is tricky, particularly without performance regressions on small files, but without solving it versioning of .iso and other large objects will continue to be extremely painful.
• Add an API for per-file graph access that alllows incremental access and is suitable for on-demand generation if desired.
• Repository stacking API. Allowing multiple databases to be stacked to give a single ‘repository’ will allow implementation of some long desired features like history horizons, and bundle usage where the bundle is not added to the local repository just to examine its contents.
• Revision data manipulation API. We need a single streaming API for adding data to or getting it from a repository. This will need to allow hints such as ‘optimise for size’, or ‘optimise for fast-addition’ to meet the various users planned, but it is a core part of the library today, and its not sufficiently clean to let us simplify/remove a lot of related code today.

1.1.5.2   Interoperable disk changes

• New container format to allow single-file description of multiple named objects. This will provide the basis for transmission of revisions over the network, the new bundle format, and possibly a new repository format as well. [Core implemented]
• Separate the annotation cache from the storage of actual file texts and make the annotation style, and when to do it, configurable. This will reduce data sent over the wire when repositories have had ‘needs-annotations’ turned off, which very large trees may choose to do - generating just-in-time annotations may be desirable for those trees (even when performing annotation based merges).
• Repository disk operation ordering. The order that tasks access data within the repository and the layout of the data should be harmonised. This will require disk format changes but does not inherently alter the model, so its straight forward to export from a repository that has been optimised in this way to a 0.16 based repository.
• Inventory representation. An inventory is a logical description of the shape of a version controlled tree. Currently we operate on the whole inventory as a tree broken down per directory, but we store it as a flat file. This scale very poorly as even a minor change between inventories requires us to scan the entire file, and in large trees this is many megabytes of data to consider. We are investigating the exact form, but the intent is to change the serialisation of inventories so that comparing two inventories can be done in some smaller time - e.g. O(log N) scaling. Whatever form this takes, a repository that can export it directly will be able to perform operations between two historical trees much more efficiently than the current repositories.
• Delta storage optimisation. We plan to change the delta storage logic to use a binary delta like xdelta rather than using line based deltas from python. These binary deltas could be done along ancestry ordering, or other arbitrary patterns chosen for their intended use. Line based deltas will still be created for cached annotations. This is still under some discussion. http://bazaar-vcs.org/PerformanceRoadmap/Xdelta
• Greatest distance from origin cache. This is a possible change to introduce, but it may be unnecessary - listed here for completeness till it has been established as [un]needed.

1.1.5.3   Possibly non-interoperable disk changes

• Removing of derivable data from the core of bzr. Much of the data that bzr stores is derivable from the users source files. For instance the annotations that record who introduced a line. Given the full history for a repository we can recreate that at any time. We want to remove the dependence of the core of bzr on any data that is derivable, because doing this will give us the freedom to:

  • Improve the derivation algorithm over time.
  • Deal with bugs in the derivation algorithms without having ‘corrupt repositories’ or such things.

  However, some of the data that is technically derived, like the per-file merge graph, is both considered core, and can be generated differently when certain circumstances arive, by bzr 0.16. Any change to the ‘core’ status of that data will discard data that cannot be recreated and thus lead to the inability to export from a format where that is derived data to bzr 0.16’s formats without errors occuring in those circumstances. Some of the data that may be considered for this includes:

  • Per file merge graphs
  • Annotations

1.1.5.4   Non-interoperable disk changes

• Drop the per-file merge graph ‘cache’ currently held in the FILE-ID.kndx files. A specific case of removing derivable data, this may allow smaller inventory metadata and also make it easier to allow two different trees (in terms of last-change made, e.g. if one is a working tree) to be compared using a hash-tree style approach.
• Use hash based names for some objects in the bzr database. Because it would force total-knowledge-of-history on the graph revision objects will not be namable via hash’s and neither will revisio signatures. Other than that though we can in principle use hash’s e.g. SHA1 for everything else. There are many unanswered questions about hash based naming related to locality of reference impacts, which need to be answered before this becomes a definite item.

1.3.1.1   Optimal case

(a motivating example of ultimate performance) Assume there is a file with exactly the right data in compressed form. This may be a tarred branch, a bundle, or a blob format. Performance in this case scales with the size of the file.

1.3.1.2   Disk case

Assume current repo format. Attempt to achieve parity with cp -r. Read each file only 1 time.

• read knit graph for revisions
• write filtered copy of revision knit O(d+a)
• write filtered copy of knit index O(d)
• Open knit index for inventory
• Write a filtered copy of inventory knit and simultaneously not all referenced file-ids O(b+d)
• Write filtered copy of inventory knit index O(d)
• For each referenced file-id:
  • Open knit index for each file knit O(e)
  • If acceptable threshold of irrelevant data hard-link O(f)
  • Otherwise write filtered copy of text knit and simultaneously write the fulltext to tree transform O(h)
• Write format markers O(1)

1.3.1.3   Smart Network Case

1.3.1.4   Dumb Network Case

Pull: same as disk case, but request all file knit indices at once and request al file knits at once. Push: same as disk case, but write all files at once.

1.3.1.5   Wants

• Read partial graph
• Read multiple segments of multiple files on http and sftp
• Write multiple files over SFTP

1.3.2.1   Functional Requirements

A push or pull operation must:

• Copy all the data to reconstruct the selected revisions in the target branch. This is the goal of push and pull after all.
• Reject corrupt data. As bzr has no innate mechanism for discarding corrupted data, corrupted data should not be incorporated accidentally.

1.3.2.2   Factors which should add work for push/pull

• Baseline overhead: The time to connect to both branches.
• Actual new data in the revisions being pulled (drives the amount of data to move around, includes the commit messages etc)
• Number of revisions in the two repositories (scaling affects the determination of what revisions to move around).

1.3.2.3   Push/pull overview

1. New data is identified in the source repository.
2. That data is read from the source repository.
3. The same data is verified and written to the target repository in such a manner that its not visible to readers until its ready for use.

1.3.2.4   Notes from London

1. setup

look at graph of revisions for ~N comits to deretmine eligibility for if preserve mainline is on, check LH only

identify objects to send that are not on the client repo

• revision - may be proportional to the graph
• inventory - proportional to work
• texts - proportional to work
• signatures - ???

1. data transmission

• send data proportional to the new information
• validate the data:

1. validate the sha1 of the full text of each transmitted text.
2. validate the sha1:name mapping in each newly referenced inventory item.
3. validate the sha1 of the XML of each inventory against the revision. this is proportional to tree size and must be fixed

1. write the data to the local repo. The API should output the file texts needed by the merge as by product of the transmission
2. tree application

Combine the output from the transmission step with additional ‘new work data’ for anything already in the local repository that is new in this tree. should write new files and stat existing files proportional to the count of the new work and the size of the full texts.

1.3.3.1   Least work we can hope to perform

• Read a subset of the full versioned paths data for the tree matching the scope of the paths the user supplied.
• Seek once to each directory within the scope and readdir its contents.
• Probe if each directory is a child tree to avoid adding data for paths within a child tree.
• Calculate the ignored status for paths not previously known to be ignored
• Write data proportional to the newly versioned file count to record their versioning.
• Assign a fileid for each path (so that merge –uncommitted can work immediately)

Optionally:

• Print the ignore rule for each ignored path in the scope.
• Print the path of each added file.
• Print the total count of ignored files within the scopes.
• Record the result of calculating ignored status for ignored files. (proportional to the number we actually calculate).

1.3.3.2   Per file algorithm

1. If the path is versioned, and it is a directory, push onto the recurse stack.
2. If the path is supplied by the user or is not ignored, version it, and if a directory, push onto the recurse stack. Versioning the path may require versioning the paths parents.
3. Output or otherwise record the ignored rule as per the user interface selected.

1.3.4.1   Changes to commit

We want to improve the commit code in two phases.

Phase one is to have a better separation from the format-specific logic, the user interface, and the general process of committing.

Phase two is to have better interfaces by which a good workingtree format can efficiently pass data to a good storage format. If we get phase one right, it will be relatively easy and non-disruptive to bring this in.

1.3.4.2   Commit: The Minimum Work Required

Here is a description of the minimum work that commit must do. We want to make sure that our design doesn’t cost too much more than this minimum. I am trying to do this without making too many assumptions about the underlying storage, but am assuming that the ui and basic architecture (wt, branch, repo) stays about the same.

The basic purpose of commit is to:

1. create and store a new revision based on the contents of the working tree
2. make this the new basis revision for the working tree

We can do a selected commit of only some files or subtrees.

The best performance we could hope for is: - stat each versioned selected working file once - read from the workingtree and write into the repository any new file texts - in general, do work proportional to the size of the shape (eg inventory) of the old and new selected trees, and to the total size of the modified files

In more detail:

1.0 - Store new file texts: if a versioned file contains a new text there is no avoiding storing it. To determine which ones have changed we must go over the workingtree and at least stat each file. If the file is modified since it was last hashed, it must be read in. Ideally we would read it only once, and either notice that it has not changed, or store it at that point.

On the other hand we want new code to be able to handle files that are larger than will fit in memory. We may then need to read each file up to two times: once to determine if there is a new text and calculate its hash, and again to store it.

1.1 - Store a tree-shape description (ie inventory or similar.) This describes the non-file objects, and provides a reference from the Revision to the texts within it.

1.2 - Generate and store a new revision object.

1.3 - Do delta-compression on the stored objects. (git notably does not do this at commit time, deferring this entirely until later.) This requires finding the appropriate basis for each modified file: in the current scheme we get the file id, last-revision from the dirstate, look into the knit for that text, extract that text in total, generate a delta, then store that into the knit. Most delta operations are O(n**2) to O(n**3) in the size of the modified files.

1.4 - Cache annotation information for the changes: at the moment this is done as part of the delta storage. There are some flaws in that approach, such as that it is not updated when ghosts are filled, and the annotation can’t be re-run with new diff parameters.

2.1 - Make the new revision the basis for the tree, and clear the list of parents. Strictly this is all that’s logically necessary, unless the working tree format requires more work.

The dirstate format does require more work, because it caches the parent tree data for each file within the working tree data. In practice this means that every commit rewrites the entire dirstate file - we could try to avoid rewriting the whole file but this may be difficult because variable-length data (the last-changed revision id) is inserted into many rows.

The current dirstate design then seems to mean that any commit of a single file imposes a cost proportional to the size of the current workingtree. Maybe there are other benefits that outweigh this. Alternatively if it was fast enough for operations to always look at the original storage of the parent trees we could do without the cache.

2.2 - Record the observed file hashes into the workingtree control files. For the files that we just committed, we have the information to store a valid hash cache entry: we know their stat information and the sha1 of the file contents. This is not strictly necessary to the speed of commit, but it will be useful later in avoiding reading those files, and the only cost of doing it now is writing it out.

In fact there are some user interface niceties that complicate this:

3 - Before starting the commit proper, we prompt for a commit message and in that commit message editor we show a list of the files that will be committed: basically the output of bzr status. This is basically the same as the list of changes we detect while storing the commit, but because the user will sometimes change the tree after opening the commit editor and expect the final state to be committed I think we do have to look for changes twice. Since it takes the user a while to enter a message this is not a big problem as long as both the status summary and the commit are individually fast.

4 - As the commit proceeds (or after?) we show another status-like summary. Just printing the names of modified files as they’re stored would be easy. Recording deleted and renamed files or directories is more work: this can only be done by reference to the primary parent tree and requires it be read in. Worse, reporting renames requires searching by id across the entire parent tree. Possibly full reporting should be a default-off verbose option because it does require more work beyond the commit itself.

5 - Bazaar currently allows for missing files to be automatically marked as removed at the time of commit. Leaving aside the ui consequences, this means that we have to update the working inventory to mark these files as removed. Since as discussed above we always have to rewrite the dirstate on commit this is not substantial, though we should make sure we do this in one pass, not two. I have previously proposed to make this behaviour a non-default option.

We may need to run hooks or generate signatures during commit, but they don’t seem to have substantial performance consequences.

If one wanted to optimize solely for the speed of commit I think hash-addressed file-per-text storage like in git (or bzr 0.1) is very good. Remarkably, it does not need to read the inventory for the previous revision. For each versioned file, we just need to get its hash, either by reading the file or validating its stat data. If that hash is not already in the repository, the file is just copied in and compressed. As directories are traversed, they’re turned into texts and stored as well, and then finally the revision is too. This does depend on later doing some delta compression of these texts.

Variations on this are possible. Rather than writing a single file into the repository for each text, we could fold them into a single collation or pack file. That would create a smaller number of files in the repository, but looking up a single text would require looking into their indexes rather than just asking the filesystem.

Rather than using hashes we can use file-id/rev-id pairs as at present, which has several consequences pro and con.

1.3.4.3   Commit vs Status

At first glance, commit simply stores the changes status reports. In fact, this isn’t technically correct: commit considers some files modified that status does not. The notes below were put together by John Arbash Meinel and Aaron Bentley in May 2007 to explain the finer details of commit to Ian Clatworthy. They are recorded here as they are likely to be useful to others new to Bazaar ...

1. Unknown files have a different effect. With –no-strict (the default) they have no effect and can be completely ignored. With –strict they should cause the commit to abort (so you don’t forget to add the two new test files that you just created).
2. Multiple parents. ‘status’ always compares 2 trees, typically the last-committed tree and the current working tree. ‘commit’ will compare more trees if there has been a merge.

1. The “last modified” property for files. A file may be marked as changed since the last commit, but that change may have come in from the merge, and the change could have happened several commits back. There are several edge cases to be handled here, like if both branches modified the same file, or if just one branch modified it.
2. The trickier case is when a file appears unmodified since last commit, but it was modified versus one of the merged branches. I believe there are a few ways this can happen, like if a merged branch changes a file and then reverts it back (you still update the ‘last modified’ field). In general, if both sides disagree on the ‘last-modified’ flag, then you need to generate a new entry pointing ‘last-modified’ at this revision (because you are resolving the differences between the 2 parents).

3. Automatic deletion of ‘missing’ files. This is a point that we go back and forth on. I think the basic idea is that ‘bzr commit’ by default should abort if it finds a ‘missing’ file (in case that file was renamed rather than deleted), but ‘bzr commit –auto’ can add unknown files and remove missing files automatically.

4. sha1 for newly added files. status doesn’t really need this: it should only care that the file is not present in base, but is present now. In some ways commit doesn’t care either, since it needs to read and sha the file itself anyway.

5. Nested trees. status doesn’t recurse into nested trees, but commit does. This is just because not all of the nested-trees work has been merged yet.

   A tree-reference is considered modified if the subtree has been committed since the last containing-tree commit. But commit needs to recurse into every subtree, to ensure that a commit is done if the subtree has changed since its last commit. _iter_changes only reports on tree-references that are modified, so it can’t be used for doing subtree commits.

1.3.4.4   Avoiding Work: Smarter Change Detection

Commit currently walks through every file building an inventory. Here is Aaron’s brain dump on a better way ...

_iter_changes won’t tell us about tree references that haven’t changed, even if those subtrees have changed. (Unless we ask for unchanged files, which we don’t want to do, of course.)

There is an iter_references method, but using it looks just as expensive as calling kind().

I did some work on updating commit to use iter_changes, but found for multi-parent trees, I had to fall back to the slow inventory comparison approach.

Really, I think we need a call akin to iter_changes that handles multiple parents, and knows to emit entries when InventoryEntry.revision is all that’s changed.

1.3.4.5   Avoiding Work: Better Layering

For each file, commit is currently doing more work than it should. Here is John’s take on a better way ...

Note that “_iter_changes” does have to touch every path on disk, but it just can do it in a more efficient manner. (It doesn’t have to create an InventoryEntry for all the ones that haven’t changed).

I agree with Aaron that we need something a little different than _iter_changes. Both because of handling multiple parents, as well as we don’t want it to actually read the files if we have a stat-cache miss.

Specifically, the commit code has to read the files because it is going to add the text to the repository, and we want it to compute the sha1 at that time, so we are guaranteed to have the valid sha (rather than just whatever the last cached one was). So we want the code to return ‘None’ if it doesn’t have an up-to-date sha1, rather than reading the file and computing it, just before it returns it to the parent.

The commit code (0.16) should really be restructured. It’s layering is pretty wrong.

Specifically, calling “kind()” requires a stat of the file. But we have to do a stat to get the size/whether the record is up-to-date, etc. So we really need to have a “create_an_up_to_date_inventory()” function. But because we are accessing every object on disk, we want to be working in tuples rather than Inventory objects. And because DirState already has the parent records next to the current working inventory, it can do all the work to do really fast comparison and throw-away of unimportant records.

The way I made “bzr status” fast is by moving the ‘ignore this record’ ability as deep into the stack as I could get. Status has the property that you don’t care about most of the records, just like commit. So the sooner you can stop evaluating the 99% that you don’t care about, the less work you do.

1.3.4.6   Avoiding work: avoiding reading parent data

We would like to avoid the work of reading any data about the parent revisions. We should at least try to avoid reading anything from the repository; we can also consider whether it is possible or useful to hold less parent information in the working tree.

When a commit of selected files is requested, the committed snapshot is a composite of some directories from the parent revision and some from the working tree. In this case it is logically necessary to have the parent inventory information.

If file last-change information or per-file graph information is stored then it must be available from the parent trees.

If the Branch’s storage method does delta compression at commit time it may need to retrieve file or inventory texts from the repository.

It is desirable to avoid roundtrips to the Repository during commit, particularly because it may be remote. If the WorkingTree can determine by itself that a text was in the parent and therefore should be in the Repository that avoids one roundtrip per file.

There is a possibility here that the parent revision is not stored, or not correctly stored, in the repository the tree is being committed into, and so the committed tree would not be reconstructable. We could check that the parent revision is present in the inventory and rely on the invariant that if a revision is present, everything to reconstruct it will be present too.

1.3.4.7   Code structure

Caller starts a commit

>>> Branch.commit(from_tree, options)

This creates a CommitBuilder object matched to the Branch, Repository and Tree. It can vary depending on model differences or by knowledge of what is efficient with the Repository and Tree. Model differences might include whether no-text-change merges need to be reported, and whether the

The basic CommitBuilder.commit structure can be

1. Ask the branch if it is ready to commit (up to date with master if any.)
2. Ask the tree if it is ready to commit to the branch (up to date with branch?), no conflicts, etc
3. Commit changed files; prototype implementation:
   1. Ask the working tree for all committable files; for each it should return the per-file parents, stat information, kind, etc.
   2. Ask the repository to store the new file text; the repository should return the stored sha1 and new revision id.
4. Commit changed inventory
5. Commit revision object

1.3.4.8   Complications of commit

Bazaar (as of 0.17) does not support selective-file commit of a merge; this could be done if we decide how it should be recorded - is this to be stored as an overall merge revision; as a preliminary non-merge revisions; or will the per-file graph diverge from the revision graph.

There are several checks that may cause the commit to be refused, which may be activated or deactivated by options.

• presence of conflicts in the tree
• presence of unknown files
• the working tree basis is up to date with the branch tip
• the local branch is up to date with the master branch, if there is one and –local is not specified
• an empty commit message is given,
• a hook flags an error
• a “pointless” commit, with no inventory changes

Most of these require walking the tree and can be easily done while recording the tree shape. This does require that it be possible to abort the commit after the tree changes have been recorded. It could be ok to either leave the unreachable partly-committed records in the repository, or to roll back.

Other complications:

• when automatically adding new files or deleting missing files during commit, they must be noted during commit and written into the working tree at some point
• refuse “pointless” commits with no file changes - should be easy by just refusing to do the final step of storing a new overall inventory and revision object
• heuristic detection of renames between add and delete (out of scope for this change)
• pushing changes to a master branch if any
• running hooks, pre and post commit
• prompting for a commit message if necessary, including a list of the changes that have already been observed
• if there are tree references and recursing into them is enabled, then do so

Commit needs to protect against duplicated file ids

Updates that need to be made in the working tree, either on conclusion of commit or during the scan, include

• Changes made to the tree shape, including automatic adds, renames or deletes
• For trees (eg dirstate) that cache parent inventories, the old parent information must be removed and the new one inserted
• The tree hashcache information should be updated to reflect the stat value at which the file was the same as the committed version, and the content hash it was observed to have. This needs to be done carefully to prevent inconsistencies if the file is modified during or shortly after the commit. Perhaps it would work to read the mtime of the file before we read its text to commit.

1.3.4.9   Interface stack

The commit api is invoked by the command interface, and copies information from the tree into the branch and its repository, possibly updating the WorkingTree afterwards.

The command interface passes:

• a commit message (from an option, if any),
• or an indication that it should be read interactively from the ui object;
• a list of files to commit
• an option for a dry-run commit
• verbose option, or callback to indicate
• timestamp, timezone, committer, chosen revision id
• config (for what?)
• option for local-only commit on a bound branch
• option for strict commits (fail if there are unknown or missing files)
• option to allow “pointless” commits (with no tree changes)

(This is rather a lot of options to pass individually and just for code tidyness maybe some of them should be combine into objects.)

>>> Branch.commit(from_tree, message, files_to_commit, ...)

There will be different implementations of this for different Branch classes, whether for foreign branches or Bazaar repositories using different storage methods.

Most of the commit should occur during a single lockstep iteration across the workingtree and parent trees. The WorkingTree interface needs to provide methods that give commit all it needs. Some of these methods (such as answering the file’s last change revision) may be deprecated in newer working trees and there we have a choice of either calculating the value from the data that is present, or refusing to support commit to newer repositories.

For a dirstate tree the iteration of changes from the parent can easily be done within its own iter_changes.

Dirstate inventories may be most easily updated in a single operation at the end; however it may be best to accumulate data as we proceed through the tree rather than revisiting it at the end.

Showing a progress bar for commit may not be necessary if we report files as they are committed. Alternatively we could transiently show a progress bar for each directory that’s scanned, even if no changes are observed.

This needs to collect a list of added/changed/removed files, each of which must have its text stored (if any) and containing directory updated. This can be done by calling Tree._iter_changes on the source tree, asking for changes

In the 0.17 model the commit operation needs to know the per-file parents and per-file last-changed revision.

(In this and other operations we must avoid having multiple layers walk over the tree separately. For example, it is no good to have the Command layer walk the tree to generate a list of all file ids to commit, because the tree will also be walked later. The layers that do need to operate per-file should probably be bound together in a per-dirblock iterator, rather than each iterating independently.)

1.3.4.10   Branch->Tree interface

The Branch commit code needs to ask the Tree what should be committed, in terms of changes from the parent revisions. If the Tree holds all the necessary parent tree information itself it can do it single handed; otherwise it may need to ask the Repository for parent information.

This should be a streaming interface, probably like iter_changes returning information per directory block.

The interface should not return a block for directories that are recursively unchanged.

The tree’s idea of what is possibly changed may be more conservative than that of the branch. For example the tree may report on merges of files where the text is identical to the parents: this must be recorded for Bazaar branches that record per-file ancestry but is not necessary for all branches. If the tree is responsible for determining when directories have been recursively modified then it will report on all the parents of such files. There are several implementation options:

1. Return all files and directories the branch might want to commit, even if the branch ends up taking no action on them.

2. When starting the iteration, the branch can specify what type of change is considered interesting.

Since these types of changes are probably (??) rare compared to files that are either completely unmodified or substantially modified, the first may be the best and simplest option.

The branch needs to build an inventory to commit, which must include unchanged files within changed directories. This should be returned from the working tree too. Repositories that store per-directory inventories will want to build and store these from the lowest directories up. For 0.17 format repositories with an all-in-one inventory it may be easiest to accumulate inventory entries in arbitrary order into an in-memory Inventory and then serialize it.

It ought to be possible to commit any Tree into a Branch, without requiring a WorkingTree; the commit code should cope if the tree is not interested in updating hashcache information or does not have a last_revision.

1.3.4.11   Information from the tree to repository

The main things the tree needs to tell the Branch about are:

• A file is modified from its parent revision (in text, permissions, other), and so its text may need to be stored.

  Files should also be reported if they have more than one unique parent revision, for repositories that store per-file graphs or last-change revisions. Perhaps this behaviour should be optional.

  XXX: are renames/deletions reported here too?

• The complete contents of a modified directory, so that its inventory text may be stored. This should be done after all the contained files and directories have been reported. If there are unmodified files, or unselected files carried through from

  XXX: Actually perhaps not grouped by directory, but rather grouped appropriately for the shape of inventory storage in the repository.

  In a zoomed-in checkout the workingtree may not have all the shape data for the entire tree.

• A file is missing – could cause either automatic removal or an aborted commit.

• Any unknown files – can cause automatic addition, abortion of a strict commit, or just reporting.

1.3.4.12   Information from the repository to the tree

After the commit the tree needs to be updated to the new revision. Some information which was accumulated during the commit must be made available to the workingtree. It’s probably reasonable to hold it all in memory and allow the workingtree to get it in whatever order it wants.

• A list of modified entries, and for each one:

  • The stat values observed when the file was first read.
  • The hash of the committed file text.
  • The file’s last-change revision, if appropriate.

  This should include any entries automatically added or removed.

This might be construed as an enhanced version of set_parent_trees. We can avoid a stat on each file by using the value that was observed when it was first read.

1.3.4.13   Selective commit

For a partial commit the directory contents may need to contain a mix of entries from the working tree and parent trees. This code probably shouldn’t live in a specific tree implementation; maybe there should be a general filter that selects paths from one tree into another?

However, the tree walking code does probably need to know about selected paths to avoid examining unselected files or directories.

We never refuse selective file commits (except of merges).

1.3.4.14   Common commit code

What is common to all commit implementations, regardless of workingtree or repository format?

• Prompting for a commit message?
• Strictness/conflict checks?
• Auto add/remove?

How should this be separated?

1.3.4.15   Order of traversal

For current and contemplated Bazaar storage formats, we can only finally commit a directory after its contained files and directories have been committed.

The dirstate workingtree format naturally iterates by directory in order by path, yielding directories before their contents. This may also be the most efficient order in which to stat and read the files.

One option would be to construe the interface as a visitor which reports when files are detected to be changed, and also when directories are finished.

1.3.4.16   Open question: per-file graphs

XXX: If we want to retain explicitly stored per-file graphs, it would seem that we do need to record per-file parents. We have not yet finally settled that we do want to remove them or treat them as a cache. This api stack is still ok whether we do or not, but the internals of it may change.

1.3.5.1   Minimal Work

1.3.5.2   API Changes

Desired API:

• Tree.get_comparision(file_id, tree)

This probably entails:

• WorkingTree.store_comparison(file_id, revision_id, sha1, comparison)
• WorkingTree.get_comparison(file_id, revision_id, sha1)
• Repository.get_comparision(file_id, revision_id, revision_id)
• merge_comparisions(comparison, comparision)

1.3.5.3   Storage considerations

It must be cheap (e.g. scale with number of intermediate revisions) to perform comparison of two historical texts. It must be cheap to perform comparison of the inventories of two historical trees.

1.3.6.1   Least work we can hope to perform

• Read all branches to get initial references - tips + tags.
• Read through the revision graph to find unreferenced revisions. A cheap HEADS list might help here by allowing comparison of the initial references to the HEADS - any unreferenced head is garbage.
• Walk out via inventory deltas to get the full set of texts and signatures to preserve.
• Copy to a new repository
• Bait and switch back to the original
• Remove the old repository.

A possibility to reduce this would be to have a set of grouped ‘known garbage free’ data - ‘ancient history’ which can be preserved in total should its HEADS be fully referenced - and where the HEADS list is deliberate cheap (e.g. at the top of some index).

possibly - null data in place without saving size.

1.3.7.1   Least work we can hope to perform

We should be able to do work proportional to the scope the user is reverting and the amount of changes between the working tree and the revision being reverted to.

This depends on being able to compare unchanged subtrees without recursing so that the mapping of paths to revert to ids to revert can be done efficiently. Specifically we should be able to avoid getting the transitive closure of directory contents when mapping back to paths from ids at the start of revert.

One way this might work is to: for the selected scopes, for each element in the wt:

1. get hash tree data for that scope. 1. get ‘new enough’ hash data for the siblings of the scope: it can be out of date as long as its not older than the last move or rename out of that siblings scope. 1. Use the hash tree data to tune the work done in finding matching paths/ids which are different in the two trees.

For each thing that needs to change - group by target directory?

1. Extract new content. 1. Backup old content or replace-in-place (except windows where we move and replace).

1.3.8.1   UI Overview

Status shows several things in parallel (for the paths the user supplied mapped across the from and to tree, and any pending merges in the to tree).

1. Single line summary of all new revisions - the pending merges and their parents recursively.
2. Changes to the tree shape - adds/deletes/renames.
3. Changes to versioned content - kind changes and content changes.
4. Unknown files in the to tree.
5. Files with conflicts in the to tree.

1.3.8.2   Ideal work for working tree to historical status

We need to do the following things at a minimum:

1. Determine new revisions - the pending merges and history.

1. Retrieve the first line of the commit message for the new revisions.

1. Determine the tree differences between the two trees using the users paths to limit the scope, and resolving paths in the trees for any pending merges. We arguably don’t care about tracking metadata for this - only the value of the tree the user commited.

1. The entire contents of directories which are versioned when showing unknowns.

1. Whether a given unversioned path is unknown or ignored.

1. The list conflicted paths in the tree (which match the users path selection?)

Expanding on the tree difference case we will need to:

1. Stat every path in working trees which is included by the users path selection to ascertain kind and execute bit.

1. For paths which have the same kind in both trees and have content, read that content or otherwise determine whether the content has changed. Using our hash cache from the dirstate allows us to avoid reading the file in the common case. There are alternative ways to achieve this - we could record a pointer to a revision which contained this fileid with the current content rather than storing the content’s hash; but this seems to be a pointless double-indirection unless we save enough storage in the working tree. A variation of this is to not record an explicit pointer but instead define an implicit pointer as being to the left-hand-parent tree.

1.3.8.3   Locality of reference

• We should stat files in the same directory without reading or statting files in other directories. That is we should do all the statting we intend to do within a given directory without doing any other IO, to minimise pressure on the drive heads to seek.
• We should read files in the same directory without reading or writing files in other directories - and note this is separate to statting (file data is usually physically disjoint to metadata).

1.3.8.4   Scaling observations

• The stat operation clearly involves every versioned path in the common case.
• Expanding out the users path selection in a naive manner involves reading the entire tree shape information for both trees and for all pending-merge trees. (Dirstate makes this tolerably cheap for now, but we’re still scaling extra-linearly.)
• The amount of effort required to generate tree differences between the working tree and the basis tree is interesting: with a tree-like structure and some generatable name for child nodes we use the working tree data to eliminate accessing or considering subtrees regardless of historival age. However, if we have had to access the historical tree shape to perform path selection this rather reduces the win we can obtain here. If we can cause path expansion to not require historical shape access (perhaps by performing the expansion after calculating the tree difference for the top level of the selected path) then we can gain a larger win. This strongly suggests that path expansion and tree difference generation should be linked in terms of API.

1.3.10.1   Needs

• Access to revision graph proportional to number of revisions read
• Access to changed file metadata proportional to number of changes and number of intervening revisions.
• O(1) access to fulltexts

1.3.10.2   Notes

Multiparent deltas may offer some nice properties for performance of annotation based merging.

1.3.11.1   Needs

• Improved common ancestor algorithm
• Access to partial revision graph proportional to relevant revisions
• Access to changed files proportional to number of change files and intervening revisions
• Use knit deltas without recomputing
• Access to knit deltas in O(1) time
• Access to snapshots in O(1) amortized time
• All snapshots must have knit deltas

1.3.12.1   Specification of uncommit

uncommit removes revisions from the head of a branch. (By default, only the very latest revision is removed, but optionally more can be taken.) Uncommit does not affect the repository (garbage collection is a separate step and not done by default). The working tree is not logically modified (revert is a different operation), except as described below about merges.

Uncommit can be performed on either a branch or a working tree (and implicitly its branch.)

If the uncommitted revisions includes one or more merges, after the uncommit those revisions are in the working tree’s list of pending merges, because their tree changes are still present in the tree.

For a bound branch, uncommit fails unless the local branch is up to date.

1.4.1.1   Introduction

The basic idea is that for a directory in a tree (committed or otherwise), we will have a single scalar value. If these values are the same, the contents of the subtree under that directory are necessarily the same.

This is intended to help with these use cases, by allowing them to quickly skip over directories with no relevant changes, and to detect when a directory has changed:

• diff/status (both local trees and historical trees)
• merge
• log -v
• log on a directory
• commit

1.4.1.2   Use-case oriented APIs

Most of this will be hidden behind the Tree interface. This should cover log -v, diff, status, merge (and implicit merge during push, pull, update):

tree.iter_changes(other_tree)
tree.get_file_lines(file_id)   # and get_file, get_file_text

find_touching_revisions(branch, file_id) # should be on Branch?

1.4.1.3   Open questions

• Is this a good idea at all?

  If changing a file changes all its parent directories up to the root it will cause more churn on commit. (We currently update the all-in-one inventory, but only have to update one line of it.)

  Every time a child changes, we’ll get a new node in the per-directory graph. This is generally useful: it allows bzr log to do the default mode easily, which is to show all changes under that directory. The less common operation, log --no-recursive is still possible by looking only at when the directory itself was renamed, added or removed. (That is what the directory graph describes in bzr 0.18 and it is rarely useful.)

• Should these be hashes or revision ids or something else?

  Pros of using hashes: hashes are easy to generate by a foreign branch plugin (e.g. bzr-svn). They don’t need to get recursive last-changed from the foreign branch, or to walk back through history. They just need the relevant directory state, which any system we support can answer.

  Hashes converge: if you modify and then modify back, you get the same hash. This is a pro because you can detect that there were ultimately no significant changes. And also a con: you cannot use these hashes to form a graph because they get cycles.

• Are the values unique across the whole tree, or only when comparing different versions of the same object?

  If we use last-changed revisions, then they will be very not unique across the whole tree. To look up the contents, you must pass a composite key like (file_id, last_changed).

  If we use hashes they will be same only when the two contain the same contents. Since we say that file ids must be unique, this means they will match if and only if they are empty. We might relax that in future when we introduce path tokens.

• Is it reasonable to assume hashes won’t collide?

  The odds of SHA-1 hashes colliding “accidentally” are vanishingly small.

  It is possible that a preimage attack against SHA-1 may be discovered in the future. Since we’re not proposing in this document to make revision-ids be SHA-1, if SHA-1 was obsoleted then we could rewrite the contents of revisions but would not need to rename revisions. So the impact of such a migration should just be a format upgrade, and a recommendation (but not requirement) to re-sign revisions.

• If we use hashes, should it be the hash of the representation stored for a directory?

  In other words, should we pun the representation of the directory with the form used for validation.

  If there’s some data stored that’s not in the hash it’s problematic. The hash in no longer (effectively) uniquely identifies the representation.

  It is desirable that we have a hash that covers all data, to guard against bugs, transmission errors, or users trying to hand-hack files. Since we need one hash of everything in the tree, perhaps we should also use it for the fingerprint.

  Testaments explicitly separate the form used for hashing/signing from the form used for storage. This allows us to change the storage form without breaking existing GPG signatures. The downside is that we need to do work O(tree) to make a testament, and this slows down signing, verifying and generating bundles. It also means that there is some stored data which is not protected by the signature: this data is less important, but corruption of it would still cause problems. We have encountered some specific problems with disagreement between inventories as to the last-change of files, which is currently unsigned. These problems can be introduced by ghosts.

  If we hash the representation, there is still a way to support old signatures, assuming that we never discard irreplaceable information. The signature should say what format it applies to (similar to testaments), and we could transform in memory the tree back to that format.

• Is hashing substantially slower than other possible approaches?

  We already hash all the plain files. Except in unusual cases, the directory metadata will be substantially smaller: perhaps 200:1 as a rule of thumb.

  When building a bzr tree, we spend on the order of 100ms hashing all the source lines to validate them (about 13MB of source).

• Can you calculate one from a directory in the working tree? Without a basis?

  This seems possible with either hashes or revision ids.

  Using last_changed means that calculating the fingerprint from a working tree necessarily requires reading the inventory for the basis revision, so that we know when unchanged files were last changed. With hashes we could calculate them using the working tree information alone. It’s true that we will often then compare that information to the basis tree (e.g. for simple bzr diff), but we may only have to compare at the top level, and sometimes we’re comparing to a different tree. This also touches on whether we should store last_modified for files, rather than directories.

  For revision ids we need to assign a value to use for uncommitted changes, but see below about the problems of this.

  In some ways it would be elegant to say (hypothetical):

  wt.get_root().get_last_modified() == branch.get_last_revision()
  

  to know that nothing was changed; but this may not be much better than

  wt.get_root().get_hash() ==
    branch.get_basis().get_root().get_hash()

• Can you use this to compare (directories from) two working trees?

  If you can generate it from a working tree, you should be able to use it to compare them.

  This does rule out for example using last_modified=None or ='current:' to mean “changed in the working tree.” Even if this is not supported there seems some risk that we would get the same fingerprint for trees that are actually different.

  We could assign a hypothetical revision id to the tree for uncommitted files. In that case there is some risk that the not-yet-committed id would become visible or committed.

• Can we use an “approximate basis”?

  When using radix trees, you may need context beyond the specific directory being compared.

• Can you get the fingerprint of parents directories with only selected file ids taken from the working tree?

  With hashes, we’d want to carry through the unselected files and directories from the values they had in the parent revision.

• Are unbalanced trees a significant problem? Trees can be unbalanced by having many directories (deep or wide), or many files per directory.

  For small trees like bzr, 744 of 874 are in the bzrlib subtree. In general, larger trees are more balanced, because humans, editors and other tools have trouble managing very unbalanced trees. But there are exceptions: Aaron has one tree with 20,000 generated but versioned entries in one directory.

• Should we use a radix tree approach where fingerprints are calculated on a synthetic tree that is by definition balanced, even when the actual tree is unbalanced?

• What are the specific advantages of using recursive-last-modified rather than hashes?

  It may be a smaller step change.

  It’s a bidirectional link: given a directory text identifier (file_id, last_changed) you can look up the revision that last changed it.

  From the preceding, even without the per-file graph you can skip through the history of this file: go to the last-changed revision, look at all its parents and repeat.

• Is it a smaller change to use recursive-last-modified on directories?

  Probably yes:

  1. We can just put it into the current inventory format without changing anything else.

     By contrast to use a hash we’d have to either split up the inventory as stored, or change the sort order for the inventory, or synthesize per-directory inventories in memory for hashing.

     However, xml is somewhat redundant and slow to parse/generate; and reading the whole thing before comparing some sections is only a partial win. It may be a smaller change but we’d be preserving things we want to change.

  1. At present we rarely hash storage representations, only file texts. This is not a large technical change, but it is a conceptual change. This has some consequences for how we can upgrade it in future: all the changed directories need to be rewritten up to the revision level.
  1. If we address directories by hash we need hash-addressed storage.
  1. If we address directories by hash then for consistency we’d probably (not necessarily) want to address file texts by hash.
  1. The per-file graph can’t be indexed by hash because they can converge, so we need to either rework or dispose of the per-file graph.

• Any possibilities for avoiding hashes recurring?

  1. Hash along with an identification of the parents (as in hg). Then you can’t convert a tree without all its basis trees, and there is still convergence when the same merge is done by two people, and you can’t create it directly from the working tree.
  1. Include last-modified revision id in the hash.
  1. Index by (revision, hash) or vice versa.
  1. Store a per-file graph and allow it to have repeated keys. The graph would tell you about all the parent texts ever seen; you would need to use revision graph information to resolve ambiguities.

• What are the specific disadvantages of using recursive-last-modified rather than hashes?

  To calculate the last-changed revision, given the last-changed information of the contained files, you need to look at the revision graph. They’re not enough because you need to know the relations between the mentioned revisions. In a merge it’s possible the correct directory last-modified will not be the same as that of any of the files within it. This can also happen when a file is removed (deleted or renamed) from a directory.

• Should we split up storage of the inventories?

  This is not quite the same but connected.

• How does this relate to per-file/per-directory hashes?

  If the version of a file or directory is identified by a hash, we can’t use that to point into a per-file graph. We can have a graph indexed by (file_id, hash, revision_id). The last-modified could be stored as part of this graph.

  The graph would no longer be core data; it could be always present but might be rebuilt. Treating it as non-core data may make some changes like shallow branches easier?

• How do you ask a tree for a given text?

  Right now we say

  revision_tree.get_file_lines(file_id)
  

  so the choice of storage is hidden behind the revision tree: it could be accessed by (file_id, last_changed) or by hash or otherwise.

  At the moment the Repository exports a friend api to RevisionTree, currently usually talking in VersionedFiles.

  We probably wouldn’t want Repository to expose a get_text_for_sha1() interface because that would be very difficult to support on old repositories or on foreign branches.

1.4.1.4   Conclusions

1.4.1.5   Design changes

1.4.1.6   API changes