The commit index

In short: each commit gets a position, and a commit's parents always have lower positions. The positions are split over a stack of segment files, each roughly twice the size of the one stacked on it. A transaction adds commits to an in-memory segment on top and writes it out when the transaction commits, merging small segments into their parents so the stack stays O(log n) deep. A file in op_links/ records which segment is the index as of each operation. The change-ID index and short ID prefixes are lookups in the same sorted tables, with visibility computed from the view's heads.

1. The traits

The repo only talks to the index through four traits in index.rs. The one implementation in jj is the default index, which lives in its own crate, jj-default-index (default-index/src/). IndexStore is the factory: it loads the index as of an operation, and writes a mutable index back and links it to the operation that a transaction just created.

A view is not an index input: the index holds every commit any operation has referenced, visible or not. Visibility is applied later, by passing the view's heads to change_id_index or by evaluating a revset against them.

ReadonlyRepo::change_id_index · MutableRepo::new calls start_modification · Transaction::write calls write_index

2. Positions and the segment stack

A GlobalCommitPosition is a u32 numbering every indexed commit. Commits are added parents first (add_commit_data looks each parent up and panics if one is missing), so a parent's position is always lower than its child's. A commit's generation number is one more than the largest of its parents', and 0 for a root. Graph walks rely on both facts to stop early.

The positions are split across segments. Each segment knows its parent segment and how many commits sit below it, so a local position plus that count gives the global one. CompositeCommitIndex is the stack as a whole. To find an entry by position, entry_by_pos walks down from the newest segment to the first one whose range contains it. A lookup by ID asks each segment in turn (entry_by_id).

The composite stack has O(log n) segments, so each lookup checks a handful of files. The stack only grows at the top, so older segments are never rewritten and can be shared by the index of every later operation.

3. The segment file format

A ReadonlyCommitIndexSegment is one file in .jj/repo/index/segments/ (layout in On-disk layout §7), read whole into memory. It holds only the commits it adds. Every integer is a little-endian u32, and the version is COMMIT_INDEX_SEGMENT_FILE_FORMAT_VERSION = 6.

load_from checks the version, reads the parent file name, and loads the parent recursively before the segment itself. A version mismatch becomes ReadonlyIndexLoadError::UnexpectedVersion, which the store treats as "rebuild" (§5). The upstream comments list two possible improvements, a trie for the repeated commit IDs and a Git-style fanout table, as TODOs.

4. The mutable segment, squashing, and saving

MutableCommitIndexSegment keeps the same data in memory: a vector of graph entries, a BTreeMap from commit ID to local position, and one from change ID to positions. start_modification stacks an empty one on the loaded index (DefaultMutableIndex::incremental). add_commit skips a commit that is already indexed. merge_in adds the commits of another index down to the segment the two share, which is how a merged operation's index is built.

When the transaction commits, save_mutable_index runs:

1. maybe_squash_with_ancestors walks down the stack. While the new commits are at least half as many as the next segment's, it absorbs that segment and adds its commits to the count. The absorbed segments and the new commits become one new mutable segment on top of the first segment it stopped at. This is what keeps each segment about twice the size of the one above.
2. save_in serializes it, names the file by the hex BLAKE2b-512 hash of its bytes, and moves a temp file into place. Identical content gives an identical name, so a racing process writing the same segment is harmless. An empty segment is not written: the parent segment is reused as is.
3. The changed-path index is squashed and saved the same way (§8), then associate_index_with_operation writes the operation's op_links file.

5. From an operation to its index

Each operation that has been indexed has a file op_links/<op hex> holding a protobuf SegmentControl: the commit segment's ID, and, if the changed-path index is on, the position its first commit sits at and its segment IDs. Several operations can name the same segment, for example when an operation added no commits.

get_index_at_op reads that file and loads the segments (load_index_at_operation). It falls back to building the index in two cases:

• No link file. This happens with an operation written by another process or by an older jj, or after jj debug reindex. build_index_at_operation walks back to the nearest ancestor operation that has a link and loads its index. It then collects every commit ID referenced by the operations in between and their views, orders them parents first (ties broken by committer timestamp), adds each one, and saves the result as above.
• Corrupt or old-format segment. It prints "Reindexing...", clears the whole index directory with reinit, and builds from scratch.

The index is therefore a cache. Deleting .jj/repo/index/ loses nothing but time. all_heads_for_gc reports every head ever indexed, hidden or not, which garbage collection uses to keep commits reachable from older operations.

6. Graph queries

Positions make the common queries cheap, because a walk toward the roots can stop at the first position or generation number that rules a commit out.

7. Change IDs and visibility

The change-ID tables in each segment answer "which commits have this change ID", but some of those commits are hidden: rewritten, abandoned, or only reachable from an old operation. resolve_change_id_prefix asks each segment in turn. It merges matches of the same ID across segments, and stops as soon as two different IDs match. The result is every position with that ID, newest first.

To tell visible from hidden, change_id_index(heads) builds a ChangeIdIndexImpl with an AncestorsBitSet seeded with the view's heads. The bit set is filled lazily: visit_until walks down from the heads only as far as the lowest position being asked about, so a lookup of a recent change touches only the top of the graph. resolve_change_targets_for_positions tags each commit Visible or Hidden, giving a ResolvedChangeTargets. Its helpers report whether any target is visible and whether the change is divergent (more than one visible target), and pick a target by the offset in xyz/1 syntax (methods).

The trait's comments spell out the consequence (impl ChangeIdIndex): the prefix search runs over all change IDs, hidden ones included. A prefix can therefore be ambiguous even when only one matching change is visible, and the shortest unique prefix is "usually a few digits longer" than the visible commits alone would need. §9 covers how the CLI narrows that.

8. The changed-path index

files() and diff_lines() in a revset normally diff each candidate commit against its parents. The changed-path index stores the result instead: for each commit, the sorted list of paths it changed. The revset engine checks it first and diffs only commits outside its range.

It is off by default. A new index starts with CompositeChangedPathIndex::null() (DefaultMutableIndex::full), which stores nothing. jj debug index-changed-paths turns it on by running build_changed_path_index_at_operation, which indexes up to --limit commits ending at the newest. From then on it covers one contiguous range of positions: add_commit appends a commit's paths only when the commit lands at the index's next position, so new commits keep being indexed. Paths come from collect_changed_paths, which diffs against the merged parent tree and returns nothing for a single-parent commit with the same tree.

The segment format (version 0) has the counts, then per commit its start in the changed-path table, that table (each commit's paths as path numbers, sorted by path), and finally the segment's own sorted table of path bytes. Unlike commit segments, a changed-path segment does not name its parent. Their order lives only in SegmentControl, so segments can be added below without rewriting the ones above. The squash rule is the same as for commit segments (maybe_squash_with_ancestors).

9. Short ID prefixes

At the index level, the shortest unique prefix of an ID is one hex digit longer than its longest common prefix with either neighbour in sorted order, computed in each segment, with the largest value kept (shortest_unique_commit_id_prefix_len). Resolving a prefix asks each segment and stops early once the result is ambiguous (resolve_commit_id_prefix; the binary search is in readonly.rs).

Unique among every commit jj has indexed is longer than a user needs. So the CLI disambiguates within a smaller set first. IdPrefixContext holds a revset, which is revsets.short-prefixes, or revsets.log when that is unset (load_short_prefixes_expression). On first use, DisambiguationData::indexes evaluates it and builds two in-memory IdIndexes over the commit and change IDs it yields. Each IdIndex is a sorted vector of the first 4 bytes of each key plus a pointer.

The resulting IdPrefixIndex answers in this order:

1. Within the set. A single match there wins (resolve_commit_prefix, resolve_change_prefix), but only if the commit exists in this repo, or the change ID still resolves to a visible commit. An ambiguous match there is final.
2. The whole repo. With no match in the set, it falls back to the repo's index and change-ID index.
3. Bookmarks and tags. The length shown is then lengthened, if needed, until the prefix is not the name of a local bookmark or tag, since those take priority when a symbol is resolved (disambiguate_prefix_with_refs).

This is why the highlighted prefixes in jj log are often one or two characters long even in a large repo, and why a prefix that works in the log can fail to resolve once the commit falls outside revsets.short-prefixes. A fresh context is created per repo view (new_id_prefix_context), so prefixes never come from a stale set.