FR: Increase computational power of revset language

[arxanas]

Is your feature request related to a problem? Please describe.

There are certain kinds of computations that I would like to perform in the revset language that I can't currently. In #4972 (comment), I give one example, where I want to find the "most recent" divergent commit for each currently-diverging change, which I argue you can't do in the current revset language:

Suppose you have X1, X2, Y3, Y4, with X/Y being the divergent change IDs and X1 having been committed before X2, etc., and you want to automatically abandon X1/Y3 in favor of the newer X2/Y4, then I don't think there's currently a way to express that. You first have to group by change ID (like {X1, X2}, {Y3, Y4}), then select the latest element from each of those groups.

More fundamentally, the revset language is currently mostly constrained to basic set operations, which limits its computational power.

To contrast, I showed the following as an example of using first-order logic to add computational power to the language and solve the problem:

A logic programming or relational model might be able to express the above more straightforwardly than the current revset language seems to naturally support. For example, you could express this:

$$ \begin{align} \text{commitsdiverge}(x, y) &= x \neq y \land x\text{.changeid} = y\text{.changeid} \\ \text{divergent}() &= \left\lbrace x : \text{Commit} | \exists y : \text{Commit} ~ \left[ \text{commitsdiverge}(x, y) \right] \right\rbrace \\ \text{latestdivergent}(D) &= \left\lbrace x \in D | \forall y \in D ~ \left[ \text{commitsdiverge}(x, y) \rightarrow x\text{.date} > y\text{.date} \right] \right\rbrace \end{align} $$

and write jj abandon -r 'latestdivergent(divergent())'.

Describe the solution you'd like

Adopt a more expressive language paradigm to be able to compute certain things in the revset language. Some axes to consider:

• Approachable: Most users will not be familiar with the language, and will want to pick it up quickly, so it should be easy and familiar.
• Efficient: It may be difficult or expensive from an engineering perspective to provide an efficient implementation of certain paradigms (or maybe not... Rust library authors have done some frightening things).
• Expressive: It should be possible to actually solve computationally-more-difficult problems, hopefully with a minimal amount of added features.
• Interactive: Most programming languages are designed to write long programs, while the revset language is primarily used at the command-line in ad-hoc invocations.
• Predictable: Computation should probably be deterministic, and generally match user intuition.

We should also keep in mind where we want to stop extending the language and instead rely on templating + scripting to perform more complex computation.

• It's interesting to note that the templating language has more flexible data structures than the revset language currently. If we need the extra power in order to produce output for other computational systems to consume, does that suggest that our own computational system's power should be increased?

Describe alternatives you've considered

Here's some of the paradigms we could adopt:

• None: We may decide that increasing the language's computational power adds too much complexity. We could rely on templating and scripting instead.
• Imperative: Add mutable state, control flow constructs, etc. as a mean to compute values with concrete algorithms, similar to most mainstream programming languages.
• Functional: Add lambdas and certain primitive functions to implement the expressive power of the lambda calculus (or a weaker total language), similar to features in many mainstream programming languages.
• Relational: Add relational queries and implement the expressive power of the relational algebra, similar to SQL or other query languages.
• Logic: Add logical quantifiers and implement the expressive power of first-order logic (or a weaker total language), similarly to Prolog, Datalog, or other logic programming languages
• Embed an entire other language: We could actually add e.g. a Python or Starlark interpreter, although this seems unnecessary to me in favor of the existing language-agnostic templating + scripting approach.
• Other?

Realistically, a functional approach seems most strategically sound to me, even though I would personally prefer a more declarative paradigm.

Additional context

• Latest revset docs: https://martinvonz.github.io/jj/latest/revsets/
• FR: make jj commands more composable #3814: Related, but the main focus is chaining jj commands together for automated purposes.
• FR: Make special forms not look like functions #4921: If we adopt a paradigm with certain evaluation semantics, it might have downstream effects on the design of the rest of the language.