Revset engine

In short: a pest grammar and a Pratt parser turn the text into an AST, and alias definitions are substituted in like macros. Lowering turns the AST into a RevsetExpression tree. Symbol resolution replaces every name with commit IDs, using the repo. Eleven optimization passes rewrite the tree, and visibility resolution turns all() and negation into walks from the visible heads, giving a ResolvedExpression that knows nothing about views. The index evaluates that into a lazy Revset, which yields commits children first. Predicates that need commit contents, such as description() or files(), are filters checked one commit at a time. File arguments use the same machinery in a smaller language, filesets.

1. The pipeline

Upstream's own walkthrough of these stages is docs/technical/revset-evaluation.md. Each stage produces a stricter type than the one before, so a later stage cannot see anything an earlier stage should have removed. The first three stages need only text and config. From symbol resolution on, the stages need a repo.

revset::parse runs the top row and returns a UserRevsetExpression. In the CLI, parse_revset wraps the result in a RevsetExpressionEvaluator, which carries the repo, the extensions and the short-prefix context to the later stages (resolve_revset, evaluate). Commands that combine their own expression with the user's, such as intersecting with mutable(), do so on the UserRevsetExpression before resolution.

RevsetExpression is generic over a state type. As a UserRevsetExpression it may still hold unresolved commit refs and operation strings. As a ResolvedRevsetExpression those slots have type Infallible, so the compiler guarantees resolution is complete.

revset-evaluation.md · ResolvedRevset · ResolvedRevsetExpression::evaluate

2. Grammar and AST

The grammar is revset.pest. Its identifier rule lets ., - and + appear between name parts, so v1.2.3 and feature-x are single symbols rather than ranges or parent operators. A primary is a parenthesized expression, a function call, a pattern such as glob:"x*", or a symbol with an optional @ (main@origin, default@, @). expression only lists operands and operators; precedence comes from the Pratt parser table in parse_expression_node. The grammar, the parser and dsl_util.rs live in their own jj-dsl crate (dsl/), which jj-lib imports (dsl_util, revset_parser). Before building the AST, parse_program estimates the tree's depth from pest's parse tree and rejects anything deeper than MAX_TREE_DEPTH (256) with "Expression nesting limit exceeded" (source), instead of crashing on deeply nested input. Each rule's depth_role says whether it adds a level; | only separates operands, since chained unions are flattened. The walk is validate_tree_depth.

The grammar still accepts the old operators ^, infix + and infix -, only so that the parser can reject them with a hint naming the replacement (-, |, ~). The old range operator : is gone from the grammar, since it clashed with the kind: prefix of string patterns such as exact:"main", so :x is a plain syntax error. Ranges cannot nest without parentheses. A bare :: and a bare .. parse to their own nodes, DagRangeAll and RangeAll.

The AST is ExpressionKind, with the operators in UnaryOp and BinaryOp. No name is looked up at this stage: main is an Identifier, main@origin a RemoteSymbol, and foo() a FunctionCall that may be a built-in or an alias.

3. Aliases

Aliases come from the [revset-aliases] config table. They can be symbols ('trunk') or functions with parameters ('f(x)'). The shared DSL code in dsl_util.rs (expand_aliases, expand_aliases_with_locals) substitutes each use with the parsed definition, recursively, and leaves an AliasExpanded node so errors can say which alias they came from. Expansion is textual, like a macro: a parameter used twice evaluates its argument twice. The same code expands template and fileset aliases.

Much of jj's default behavior is defined as aliases in cli/src/config/revsets.toml, which users can override:

The [revsets] table above it holds the default revset for each command that has one, such as log = "builtin_log()" and arrange = "reachable(@, mutable())". The CLI checks that commands do not rewrite immutable commits by parsing immutable_heads() on its own and adding root() (parse_immutable_heads_expression).

4. Lowering to RevsetExpression

lower_expression turns each AST node into a RevsetExpression. Operators become the same nodes as their function forms, so ::x and ancestors(x) are identical from here on:

Functions are looked up by lower_function_call in a map that starts as BUILTIN_FUNCTION_MAP plus any extension functions. An unknown name is an error that suggests similar names, aliases included. Each RevsetFunction checks its own arguments: description() parses a string pattern and returns a filter, files() parses a fileset, and at_operation() keeps its operation argument as unparsed text.

The commit refs that later need the repo are RevsetCommitRef: WorkingCopy, WorkingCopies, Symbol, RemoteSymbol, ChangeId, CommitId, Bookmarks, RemoteBookmarks, Tags and RemoteTags.

5. Symbol resolution

resolve_user_expression walks the tree with an ExpressionSymbolResolver and replaces every commit ref with Commits(ids) (resolve_commit_ref). Bookmark and tag functions read the view; @ reads the view's working-copy commits. A plain symbol goes to the SymbolResolver, which asks a chain of PartialSymbolResolvers and takes the first answer (resolve_symbol):

1. a tag of that name (TagResolver);
2. a local bookmark of that name (BookmarkResolver);
3. a commit ID prefix;
4. a change ID prefix;
5. resolvers added by extensions (SymbolResolverExtension).

An empty symbol is an error, and a symbol nothing resolves is a "no such revision" error with suggestions. The ID prefix resolvers use the short-prefix context from default_symbol_resolver, so a prefix is first looked up within revsets.short-prefixes, the same way the commit index page describes for display.

Two functions change how resolution works (the resolver's fold):

• present(x) resolves x in its own scope and turns "no such revision" and "workspace has no working copy" errors into none(). Other errors, such as an ambiguous prefix, still fail.
• at_operation(op, x) loads the repo at that operation, resolves x there, and wraps the result in WithinVisibility so it is evaluated with that operation's heads. The extra repos are kept on the ResolvedRevset, whose evaluation then merges their indexes with the current one.

6. Optimization

optimize runs eleven rewrite passes in a fixed order, each over the whole tree, and each enabling later ones. The upstream walkthrough lists every rule; the gist is:

Passes 2 and 10 are inverses on purpose: unfolding exposes the parts to the passes in between, and folding puts back the forms the engine evaluates fastest. A negation left as ~x costs a walk over every visible commit, so the last passes try to remove it.

7. Visibility

The index stores every commit any operation has seen, visible or not. It has no idea what the current view is. resolve_visibility bakes the view into the expression through a VisibilityResolutionContext (its resolve) and produces a ResolvedExpression:

• all() becomes the ancestors of the visible heads plus every referenced commit, so all() & x is still x when x names a hidden commit.
• visible_heads() and root() become literal commit ID lists.
• ~x becomes all() ~ x, and x:: becomes a DAG range up to the visible heads.
• Filters move into a separate ResolvedPredicateExpression. An intersection whose right side is a filter becomes FilterWithin { candidates, predicate }; a filter on its own becomes FilterWithin over all().

ResolvedExpression has no All, NotIn, Filter or commit-ref variants, so the engine cannot meet them. ResolvedRevset::evaluate runs optimize and this step, then hands the result to Index::evaluate_revset.

8. Evaluation in the default index

Index::evaluate_revset is the extension point: another index implementation can evaluate a ResolvedExpression its own way. The default commit index passes it to revset_engine::evaluate, which builds a tree of InternalRevsets. Each one yields index positions in descending order. Because a commit's parents always have lower positions, descending position order is a valid topological order, children first, and two sets can be combined by merging their position streams without sorting.

The full case list is EvaluationContext::evaluate. The result is wrapped in RevsetImpl, which implements the public Revset trait (impl): stream of commit IDs, commit_change_ids, stream_graph for jj log, is_empty and count_estimate (both async), and containing_fn, a membership test that advances the walk only as far as the commit asked about.

9. Filters and extensions

A filter is a predicate the index cannot answer from the graph alone. RevsetFilterPredicate lists them: ParentCount, Description, Subject, author and committer name, email and date, File, DiffLines, HasConflict, Signed, and Extension. build_predicate_fn turns each into a function of an index position. Only ParentCount is answered from the index entry; every other filter loads the commit from the store, which is why pass 8 pushes filters as late as possible. File first tries the changed-path index and diffs the trees only when it has no entry (source). divergent() is a predicate too, computed from the change-ID index (evaluate_predicate).

Programs built on jj-lib extend the language through RevsetExtensions (impl):

• add_custom_function adds a function to the map, and panics if the name is taken;
• add_symbol_resolver adds a resolver at the end of the chain in §5;
• a RevsetFilterExtension is a custom filter whose matches_commit is called per commit.

The extensions reach parsing through RevsetParseContext, which also carries the alias map, the user's email for mine(), the current time that date patterns are resolved against, and the workspace.

10. Filesets

Path arguments, as in jj diff src/ or files(), use a second, smaller language built the same way: its own pest grammar and parser, the same alias expansion, then resolve_expression into a FilesetExpression of None, All, Pattern, UnionAll, Intersection and Difference. There is no symbol resolution: a bare name or string is a FilePattern, by default a glob matching that path and everything under it, relative to the current directory. ~x becomes all() ~ x. The only built-in functions are none() and all() (map).

to_matcher compiles the expression into a Matcher, the type that tree diffs and walks take (build_union_matcher groups patterns of the same kind into one matcher). Command-line paths go through parse_maybe_bare, which treats text that does not parse and has no operator characters as a plain path, while parse is strict.

FilesetParseContext · files() parses its argument as a fileset