Trees, files and copies

In short: a commit doesn't point at one tree but at a Merge<TreeId>. Usually that merge has one term, a plain snapshot. After a conflicted rebase or merge it has 2n+1 terms, and every path is looked up in all of them at once. A path's value is then a MergedTreeValue = Merge<Option<TreeValue>>, which is resolved when all terms agree after trivial merging. The trees themselves are immutable, content-addressed objects in the backend, so two commits with the same contents share their tree IDs.

1. From commit to file contents

2. Tree: one directory

There are two Tree types. The stored one, backend::Tree, is just entries: Vec<(RepoPathComponentBuf, TreeValue)>. The entries "must be sorted (by RepoPathComponentBuf's ordering) and must not contain duplicate names", which from_sorted_entries checks with a debug_assert!. Lookup by name is a binary search (entry, value). The in-memory tree::Tree wraps it with the Store, the directory path it lives at, and its TreeId, and adds path_value, sub_tree and sub_tree_recursive for walking down (source).

A subdirectory is just an entry whose value is TreeValue::Tree(id). There is no separate directory object, so a tree only stores its direct children, and an empty directory can't be represented. Every backend must give all empty trees the same ID regardless of path (Backend::empty_tree_id).

3. TreeValue

TreeValue · CopyId::placeholder

There is no conflict variant. Conflicts aren't stored inside trees any more: they live one level up, as several whole trees in the commit's Merge<TreeId>.

4. MergedTree and MergedTreeValue

MergedTree is "a lazily merged view of a set of trees": store, tree_ids: Merge<TreeId> and labels: ConflictLabels (one label per side, used in conflict markers). Nothing is merged up front. Each operation walks all the terms together and merges only the entries it touches.

A path's value is MergedTreeValue = Merge<Option<TreeValue>>: one optional value per term, where None means "absent in this term". Helpers on MergedTreeValueExt classify it: is_tree (present and every term is a tree or absent), is_file_like (present and not a tree), and to_file_merge, to_executable_merge and to_copy_id_merge, which pull one field out of each term when every term is a file or absent. When the terms of a Merge<Tree> are looked up by name, TreeMergeExt::value first tries resolve_trivial, so a path that only one side changed comes back resolved.

5. Tree diffs

Comparing two merged trees yields a TreeDiffStream of TreeDiffEntry { path, values: BackendResult<Diff<MergedTreeValue>> }, a stream rather than an iterator "so high-latency backends (e.g. cloud-based ones) can fetch trees asynchronously". Every diff goes through one engine, TreeDiffStreamImpl, created with the store's concurrency as its limit (diff_internal):

• TreeDiffVisitor handles one directory at a time. It merge-joins the entries of the "before" and "after" trees by name, keeps only changed entries the matcher accepts, and schedules a read of both sides for any entry where either side is a tree, missing sides counting as empty trees.
• The walk itself is the generic OrderedTreeWalk in tree_walk.rs. Its TreeWalkQueue runs at most that many reads at once, starting the smallest paths first (PrioritizedFutures), and holds finished entries in runs keyed by path. An entry is emitted only once no smaller path still has a read pending, so the output is in path order: a directory before its contents, and a directory's entries before later siblings. It stops starting reads while 10,000 entries are waiting.

6. MergedTreeBuilder

New trees are written with MergedTreeBuilder: start from a base MergedTree, record overrides, then write_tree(). There are two setters (source): set_or_remove(path, Option<TreeValue>) takes a resolved value (None deletes), and set_or_remove_merge(path, MergedTreeValue) takes a Merge that must be resolved or have exactly as many sides as the base tree, else it returns ConflictArityMismatchError. To combine paths from a differently conflicted tree, the source says to merge the trees instead. With no overrides it returns the base tree unchanged. Otherwise it first tries to resolve each conflicted override on its own (resolve_file_values, several at once), then puts the overrides in a path tree and rewrites every term of the base in one pass (source). The pass is the shared tree rewriter, rewrite_trees: it reads each tree that has an override at or below it, asks a visitor for the new entries, and writes the new tree once its changed subtrees are written, with at most store.concurrency() reads and writes in flight (source). A rewritten tree whose entries match the tree it was read from isn't written again; the original's id is reused (source). Each tree is rewritten once per path, id and context. The builder's context is the term index only under a conflicted override, so a subtree the terms share is read and written once (source). A non-tree override at a path wins over overrides below it. A file in the base with overrides below it becomes a directory, unless those overrides only remove paths. Subtrees that end up empty are dropped (source). If the written trees are trivially the same the result is one resolved tree; otherwise the root ids are simplified together with the base's conflict labels. The whole tree is no longer re-merged, so the base is expected to have its conflicts resolved already (source). The working-copy snapshot and most rewriting commands produce their trees this way.

7. Copies

Copy support has two halves, at different stages. See the design doc, docs/design/copy-tracking.md.

Detected copies: CopyRecord

CopyRecord describes one copy event: target path, target_commit, source path, source_file (a FileId) and source_commit. Backends produce them on demand with Backend::get_copy_records(paths, root, head), a stream in reverse-topological order. The Git backend computes them by running gix's rename and copy detection between the two commits' trees, skipping symlinks (source). The simple backend returns an empty stream.

CopyRecords indexes a batch by source and by target. A path that appears as the source or target of two different records is marked conflicting and ignored. Duplicates of the same (source, target) pair, which a merge commit reports once per parent, are skipped. copies_tree_diff_stream then rewrites a plain diff: an entry whose path is a copy target gets its source attached and is classified by resolve_copy_source as a Rename if the source is gone (or became a directory) in the target tree, and as a Copy otherwise. Those lookups run asynchronously, up to the store's concurrency limit at a time, with output kept in diff order. The separate "deleted" entry for a renamed source is dropped. This is what jj diff uses to show renames.

Tracked copies: CopyHistory

The other half is persistent identity. CopyHistory holds a file's current_path, its parents: Vec<CopyId> (none for a new file, one for a copy or rename, several for a merge of files) and a salt to give a logically new file a fresh ID. A file's TreeValue::File.copy_id names its history, which is "unchanged when a file is modified". RelatedCopy pairs an ID with its history, and Backend::get_related_copies returns the whole family. MergedTree::copy_value finds a file by copy ID.

At this pin neither built-in backend implements it. The Git backend answers read_copy, write_copy and get_related_copies with Unsupported: "The Git backend doesn't support tracked copies yet" (source), and the simple backend with "The simple backend doesn't support copies". So in a normal repository renames come only from detection.