TL;DR; All the questions that we needed to clarify for
Changeset Evolution
to complete have been answered.
We are now working on having a final implementation enabled by default in
Mercurial core.
In the past couple of years, multiple important milestones have been reached
for the Mercurial's Changeset Evolution project.
Changeset Evolution allows for simple, safe and powerful exchange of draft
changesets that can be rewritten by a distributed team.
(The concept is also useful locally, but most innovative part are the
distributed ability).
Those progresses are the result of a combined effort of a dozen people, thanks to
all of them.
In particular, we have been working on final algorithms for two of the central
concepts of changeset evolution: exchanging markers and automatic resolution
of instabilities.
They now just need a final implementation in Core.
In addition, the last uncharted territory, the restoration of older
evolutions of changesets, have been explored.
We discovered that we have to track more data regarding changeset folding to
perform this task well.
This will trigger what we expect to be the last update in tracked data and
marker format.
There are many improvements made apart from the ones we just highlighted, and
we'll go over them later in this post.
However, the highlighted ones are important milestones.
All the major algorithms questions are now cleared, we know how each complex
issues will be handled and what associated data storage we need.
Removing unknowns on those questions was a priority because they can have a
high impact on how we design user interfaces and on-disk data formats.
Two things that are complicated to change afterwards.
Now that all those areas have been explored, we have a clear sight of the route to
Evolve completion and can focus on actions directly moving toward this goal.
We need to polish and upstream the concept and code that are still inside the
Evolve extension.
Some of that code is already in a good shape to go upstream.
The road is clear, but there is a lot to carry along, any kind of help is
welcome!
Summary of work done since 2017
In general, all areas received many fixes, improvement, and polish. Some
important areas made significant progress:
Vocabulary changes
Evolution provides powerful features, capable to handle complex issues.
We must do all we can to smooth this complexity, in particular when it comes
to naming new concepts.
To address multiple feedback regarding the naming scheme, a group of people
dedicated a significant amount of time to come up with a new naming scheme for
most of the changeset evolution concept.
The resulting scheme was then enforced in Core Mercurial, the Evolve
extensions and Tortoisehg:
- Instability replaces Troubles
- Unstable replaces Troubled
- Predecessor replaces Precursor
- Orphan replaces Unstable
- Content-divergent replaces Divergent
- Phase-Divergent replaces Bumped
Check the
wiki page associated with the renaming discussion
for details.
In addition, we made some update to command and flag names:
- The
hg uncommit command is merged into hg amend as hg amend --extract
- The unloved
hg prune --biject flag has been renamed to hg prune --pair
Obsolescence History
To make distributed history edition manageable by the users involved, it is
important to make it easy for someone to understand what happened outside of
its local repository.
Changeset evolution tracks the change to all changesets that have been rewritten.
This information is valuable for many different facets, for example for
displaying what happened to a changeset, or automatically stabilize it.
We made multiple improvements to make sure the information tracked was more
informative and better put to use.
Previously the obsolescence information was mostly used to detect and resolve
instabilities.
Obsmarkers now store more data:
- the effect of an obsolescence marker (message change, patch change, etc),
- the operation that created it (amend, rebase, ...),
- possibly record a user-defined note.
And that data get used in more places:
- New
hg obslog command that displays the evolution of a changeset,
- Display successors and predecessors in
hgweb when appropriate,
- Point at latest successors of obsolete changeset in
hg log,
- Point to latest successors of obsolete working copy and accessed hidden changesets.
This greatly improved users ability to understand evolution that they, and their
team members, have performed.
Making Changeset Evolution more accessible to people unfamiliar with it.
This area is in a very good shape, there are multiple possible improvements,
but overall we have the feature we need to provide a reasonable experience.
A good share of them have been implemented in Core already, the rest needs to
be upstreamed.
See the "What next?" section for possible future improvements in this area.
History Rewriting Commands
Smooth distributed history rewriting requires a good set of commands to rewrite
history.
They need to be easy to use and to record the user intend well so that we can
leverage it.
Changesets evolutions allow more flexible history editing but also rely on
the user using the right command for the right operation to build a useful
evolution history.
A quality evolution history provides the user with the best experience.
To achieve this goal we need a clear, compact and powerful set of command to
edit history.
Progresses were made on existing commands and new commands:
hg fold got flags to clarify its two modes --from and --exact, (We are
not entirely happy with the result yet)hg uncommit is now available as hg amend --extract. This reduces the
number of commands and closes the debate about the uncommit name,hg amend gains a new --patch flag to directly edit changesets diff,- The
hg grab alias got upgraded to a full hg pick command (with proper
--abort/--continue support). The command is a mix of graft and rebase.
The command can be used to reorganize a stack of changesets.
An important milestone is the introduction of a rewind command. It is a
command to restore a stack of changeset to a predecessors state.
The command is at an early stage and will need some time to mature, however,
it is already useful and part of some people main workflow.
Implementing the rewind command was part of our exploration of the evolution
problem space.
And, indeed, we gathered very important insights.
The hg rewind command can automatically find and restore predecessors of
other changesets.
To do so, it walks the evolution graph, but it does it in the opposite
direction than the hg evolve command.
It turns out that, in the same way we had to store special information for
split, we will need extra information to properly differentiate fold from
divergences resolutions.
We currently do not have this information.
This is a good example of data requirement we had to discover early in order to
shape a functional changeset evolution in the end.
Obsolescence-markers exchange
Changeset Evolution core purpose it to unlock history edition in a distributed
setting.
To achieve this goal, the exchange of obsolescence information between
repositories is critical.
The question of which obsolescence markers should be exchanged during push and
pull have been solved a while ago.
Further testing in diverse environment setups have confirmed this logic is
correct.
However, at the start of 2017, an important issue remained: how to discover
which markers are missing on the other side?
Without an efficient way to detect them, we could not provide an efficient
synchronization of the obsolescence data.
Fortunately, we developed an algorithm and protocol that can perform an
efficient discovery for obsolescence markers.
In our daily usage on the Mercurial repository, this saves us the extra minute
we were spending on obsmarkers discovery using the previous method.
The data structure used by this algorithm scale well with repository size,
an important point that qualifies this solution for all usages.
This new method got tested in various settings and it will be used by default
in the next version of the Evolve extension.
In addition one data structure we developed for this algorithm, "stablerange",
will likely be useful to help with exchanges and caching of other data.
It could be used for pull bundle caching decisions.
The main goal of the current implementation was to validate the approach and
the scaling property of our algorithm.
Its performance and cache storage implementation is not great and this will
have to be reworked when upstreamed.
Workflow and stack
Something important connected to evolution is the clear definition of the
group of changesets related to the current user work.
Such clarity is a great help to provide good behavior and information to the
users regarding possible instability in their current work.
We made many progress in this area in the past couple of year.
In particular:
- Automatic instability resolution, using
hg evolve, restrict itself to
the current topic by default.
Avoiding selection of unrelated changeset during stabilization, something
that has been confusing users.
- The
next and prev commands are also restricting themselves to the current
topic, making their movement more predictable and useful.
- The
hg stack command allows for a quick view of the work in progress,
including listing changeset in a semantic order, same as if they were all
stabilized.
This work also offers a simple, yet powerful, workflow for feature branching in
Mercurial.
Having topic tightly linked to phases make them a good tools to enforce a healthy
phase movement practice in a project.
Since Changeset evolution is also tightly coupled with phases, healthy phase
movements is important here. Here are the progresses made:
New server repository mode: changeset with topic stay draft of push, other
get published. This is especially useful as it bridges the gap between publishing and
non-publishing repository.
Using this mode by default will preserve backward compatibility with
current Mercurial behavior regarding phase movement while allowing the
user to opt in from the client side for exchanging drafts when they want
to.
New push flag --publish: to publish selected changeset on push.
There have been various improvements on topic usability. Notably:
- clarification of topic activation, state, and movement on push/pull and
publish,
- ability to force new draft commit to have a topic (or automatically assign
a random one),
- improved topic discoverability with
hg topic --age,
- Introduction of a
s0 label referring to the parent of the topic root
- update to
s0 will keep the topic active, making insertion of new
changeset at the start of the topic simpler
- hg prev can go down to
s0
We are getting good feedback from people using this workflow.
We would like to upstream all these improvements.
Some of them are not really attached to topic (eg: hg push --publish) but we
feels like topic is overall a good branching solution for Mercurial and would
like to see it more of it upstream.
Instability Management
This is a critical part of Evolution and we made many important progress in
this area.
Exchanging draft changesets can bring "instabilities" in one's repository.
We can use various strategy to reduce the odds for it to happen, however,
given the distributed nature of Mercurial, we cannot guarantee it won't.
Because instability can happen, we need a good automatic resolution of it.
We are now is a pretty good shape.
The hg evolve command can now keep tracks of multi-step operations unlocking
important features:
- Good handling of evolution interrupted by merge conflict,
--abort,
--continue and --stop flags works as expected. (for both hg evolve and
hg next)
- Automatic stabilization of situation involving and orphan merge,
- Automatic stabilization of phase-divergence in most complex case,
- Automatic stabilization of content-divergence in most complex case.
So we now have all the instability types well under control.
There are still some corner case involving split, fold or merge that remain to
be properly handled.
However, the core tool to handle them now exists.
With all these improvements to hg evolve and hg next, we will be able to
update the default behavior of this two commands to something final, and
upstream them (more about this in the next section).
What next?
This section focus on concrete actions to bring Changeset Evolution to
completion.
It is intended for people with some knowledge of Mercurial internals.
Summary
The most important things to clear up right now is that need for better
tracking of fold.
Fixing it right might eventually affect disk storage and various algorithms.
Getting this out of the way as soon as possible is important.
In the same move, we need to mature the hg rewind command.
Easy undo is a critical item if we are to hand changeset evolution to all
users.
In parallel, there are multiple areas in the Evolve extension that are ready
to be cleaned up and upstreamed (obsmarkers discovery, cache, internal
rewriting toolkit, …).
We should also resume the upstreaming of the improvement regarding stacks
management and publishing workflow contained in the topic extension.
At first, this area might seem unrelated to enable changeset evolution into
Core, in practice the clarification in working set and publishing workflows
greatly reduce complexity around local and distributed work on draft changesets.
So time spent improving these areas is well balanced by the one we do not have
to spend solving more complex user experience issue elsewhere.
Finally, there are a couple of areas we that are mostly done but need to focus to
be wrapped up.
This is mainly about the history rewriting command and automatic instabilities
resolution.
In these cases, there are small actions to take before freezing the user
experience in Core.
Of course, more improvement will be made to them once into Core.
However such improvement does not seem necessary to enable evolution by
default.
Internals
Fold tracking
We need better tracking of fold operation.
This is necessary to provide a fully functional hg rewind command.
This command is important because users need a simple way to undo mistakes.
We need to update the marker creation API and to store this information.
Such change might impact the on-disk storage format and more.
The way we currently store split have a couple of quirks (eg: when only some
of the split successors are exchanged). The current ideas for storing fold
data could also be applied to split, handling these cases better than with the
current split encoding. Tracking splits and folds is a quite interresting
issues, we'll get back to it in an independant blog post.
These possible low-level changes makes the tracking of fold a priority target.
Upgrading up-disk storage of existing users is never simple and it might also
affect multiple algorithms that will have to cope with a different split
encoding.
History rewriting toolkits
To power its history rewriting commands and its UI, Evolve has a full toolkit
for building history rewriting commands.
This toolkit is ready to be upstreamed and would be a good first step toward
upstreaming the commands, free of any question related to user experience.
Evolution history
All the current work done around better evolution history is either already
upstream, or ready to be upstreamed.
We should keep that effort going.
There is one extra feature that users have been requesting, a clear
transaction log to keep trace of what exactly happens from each past
operations.
This would be especially useful on push and pull as they may introduce many
changes from other people in one repository.
This would fit the journal extension, making it tracking a wider amount of data.
This is not a road blocker, but it would be nice to have.
Commands
The Evolve extension provides multiples commands, most of them are close to be
"done" enough for our goal of Evolve enabled by default in Core.
Rewind command
The one command that needs serious attention to mature is the rewind command.
Users can "rewind" evolution of stack of changeset using this command.
The first version of this command revealed we needed to record more data about
changeset folding.
Once this data is available we should have all the pieces to build a final user
experience for this command.
Having this command is very important for the Changeset Evolution experience.
To trust the tool, users need to be confident they can undo their mistake.
History rewriting command
Over the year history rewriting commands in the Evolve extension evolved into a
pretty solid base.
As mentioned in a previous subsection, the internal toolkit powering these
functions could be upstreamed now.
The commands themselves need various adjustments to ensure consistency and
solve some long lasting questions (those we'll cover in the second part of this blog post).
All these adjustments are small and should be easy to perform.
That last round of polish is best done in Evolve extension to offer it the
wider testing possible before we settle it down.
Here are examples of small adjustment we need to do:
- The
hg amend --extract need to expose a flag similar to hg uncommit --rev
before can fully drop the older command,
- Currently
hg fold requires either one of --from or --exact.
We should pick one to be the default.
--exact has a bit more mercurial developer supporters, but also requires the
user to learn some revsets which is bad.
If we have access to the shorter in-stack reference from topic (s1, s2, etc),
the hg fold s1+s2 form might be good enough.
Provided we give a proper example of how to use this in the documentation.
- The
hg split comment is inconsistent with other similar commands (amend,
revert, uncommit, etc).
It does not accept filename and is interactive by default.
We should align its behavior with the other commands.
Of course, this command-set will keep getting larger improvements.
For example, ideas have been floating around about making it easier to control
changeset order in the stack via new commands flags.
However, those improvements are not on the critical path to enable changeset
evolution in Core.
So we don't plan to spend time on them until then.
Automatic evolution
There has been a long-standing debate: should we automatically evolve
descendants of rewritten changesets".
Automatically evolving orphans provide a smoother experience to users in many
cases but come with multiple drawbacks:
- It can trigger merge earlier than the user wants, forcing them to switch
content from the changeset they were currently rewriting.
- When rewriting all changesets in a stack, automatically evolving all
descendant means the creation of an
O(len(stack)²) changesets.
N² complexity scale very badly and this can have a very dire impact on
users repository and overall experience.
So we tend to focus users into gradual evolution instead.
This issue is referred as "obs markers explosion".
However, there has been a large demand for automatic evolution at least in some
cases.
Some command can guarantee they won't introduce conflict, lifting related
concern.
We could even consider extending that logic to all command as long as no
conflict is detected.
The N² obsmarkers explosion is trickier because all command could possible
triggers it.
Math does not really make compromises, N² is unsustainable for most values of N.
However, we still have room for improved experience.
We could imagine allowing auto evolution if the number of descendants is small
(maybe 4 or 5), or try to detect repeated rewrite in the stack.
Once we detect a problematic pattern or stack size, we could skip auto
evolution and redirect the user toward a helpful documentation page.
The hg stack command provided by the topic extensions provide a clear view of
the current work in progress, even when orphans are involved.
It is a good tool to reduce the user surge to run hg evolve --all
prematurely.
Instability prevention
A good way to avoid exposing users to the complexity inherent to instability is
to avoid creating it in the first place.
Core mercurial already have some mechanism that history rewriting commands can
use to check if their planned rewrite is valid.
However, we need to make sure it is used by all history rewriting operation and
that it catches all the instability types we want to prevent.
Obsmarker Discovery
All the logic we use for obsmarkers discovery is sound and ready to be
upstreamed.
However, the code will have to be rewritten as it gets in.
The current implementation evolved from a multi-step experiment, and use too
many complicated indirections and is not very effective in general.
Some of the cache storage we use is also problematic and will have to be
re-implemented.
In practice, most of the data we cache are not volatile.
They are an inherent property of changeset, so we could imagine storing these
value directly into a "changelog v3" format instead of keeping an independent
cache structure.
I expect the discovery to keep being improved over time, however, these
improvement can come later and are not in the critical path for enabling
evolution in Core.
The work needed to upstream this is well defined but significant.
Finding other use cases for the stablerange data might get more people
interested in making it happens.
The caches used for obsmarkers discovery shares a lot of code with other
performance related caches that should move upstream too.
Stack and workflow
The topic extensions provide various features that contribute to providing a
smooth Changeset Evolution experience. While not strictly necessary these
features simplify the task of making changeset evolution accessible to all
users.
Stack definition
One of the core features of topic is the clear definition of the current working
set: the stack.
As each changeset explicitly carries the topic information, there is no room for
ambiguity.
Related changesets that a user is actively working on are not always linear.
Either the user action or the instability brought in by distributed rewriting
can spread them on multiple topological branches.
The clear stack definition from topic handle these situations, making it an
ideal candidates.
This stack definition simplifies operation around evolution.
For example, restricting most operations within the current stack make things
much more predictable: hg prev and hg next ignores other unrelated
changesets; hg evolve only select items in the stack.
Having a predictable outcome for these commands is important for users to trust
them.
Without clear stack boundary, the behavior of there command becomes either more
limited or more complicated to explain.
The stack defines a limited number of changeset relevant to the current situation.
A small number allows for better UI.
For example, we can provide a hg stack command that displays orphan changeset
as if they were already evolved.
This provides a preview of the final structure of their stack, even if some of
it is still orphan.
This is a powerful tool to make changeset evolution accessible to all kind of
users.
The limited amount of changeset make it possible to bring back incremental
numbers to refer to a changeset.
With topic the first item in the stack is nicknamed "s1", the second "s2".
This is very useful to refer to changeset without having to copy paste obscure
hash around.
The numbering is also preserved across rewrite, making them useful for a longer
time.
Changeset Evolution empower commit centric workflow and "s#" alias make it
easier to reference individual commits.
In practice, other ways to define resilient stacks that provide this benefits.
For example, a stack definition based on phases and named-branch would do.
Named-branches are a strong fit for long-lived branches, but they have life
cycle limitations.
Topic feels like a better solution for feature branching.
Exchange and Publishing workflow
Another interesting aspect of topic is how their life cycle is tied to phases.
Changeset Evolution can be used on the non-public part of history, and for
sanity reason, this part should stay fairly limited.
Nobody wants to see a six-month-old changeset rewritten, creating tons of orphan
changesets in the process.
A core property of topic is to fade away when they are published.
This means that accepting a topic into the main branch requires to publish it.
Having a workflow step that explicitly involves publishing make sure the set of
non-public changeset remains reasonable.
Topic also solves another pain point with regarding phases.
The main purpose of Changeset evolution is to unlock distributed collaboration
on draft changesets.
However, the current default for any Mercurial server is to publish changeset on
push … so long for exchanging drafts.
It is possible to configure the server to no longer publish on push but this
has multiple drawbacks.
First, this is a server-side config, usually more complicated to setup.
Second, it means the phase cycle has to be manually though about and handled for
all changesets.
Finally, the change affects all users, you can't have a small group of advanced
users playing with advanced feature without impacting other users.
A common workaround is to have two repositories, a publishing, and a
non-publishing one.
This makes things more complicated than we would like.
Because topic is a new concept that people have to opt-in, we have more
flexibility there.
We could have a new default mode for servers where changesets are published on
push as usual unless they have a topic.
This way, users can opt-in draft changeset exchange without server side
configuration and without impacting the other users.
And since exchanging draft requires them to have a topic, they won't interfere
with the usual branch resolution of users not interested in the topic.
This offer a smooth path to draft changesets exchange without breaking backward
compatibility.
As a bonus that scheme force draft changeset to explicitly belong to a feature
branches.
To deal with phases cycle, the topic extensions provides various options:
- A new
hg push --publish flag to push that make a push publishing even when
pushing to a non-publishing server
- A config option to have server behave as described above (non-publishing for
topic only).
The topics also comes with small workflow improvement, like intuitive rebase
destination, making it easier to use.
One of the key improvement is the ability to push a new topic to a server
without --force.
Removing the cumbersome need to use this dangerous flag.
Upstreaming
The concept explained above are in a good overall shape, and we got good
feedback on them.
So, what would it take to add support for all this stack and workflow related
concept upstream?
Some of them are clear and good workflow improvement not strongly related to topic:
- The
hg push --publish option proved very useful,
- The experimental config option to limit a repository to 1 head per name
should learn about closed heads and graduate from experimental.
Some of the "stack" related logic is also independent of topic and could be
first implemented around named branches.
- "s#" alias for changeset in a stack,
- Feature from
hg stack (eg: evolution aware order),
- Constraint to the range of
hg evolve, hg next and hg prev.
Finally, there are interesting pieces directly related to topic:
- The
topic manipulation commands and lifecycle,
- The new publishing mode for servers,
- The ability to push new topic without --force.
General performance and cleanup work will be needed.
However implementing these specific features directly in Core will be
significantly simpler than from the extension.
Instability Management
Commands changes and upstreaming
There are some incoming change to hg next: The clear definition of a working
set to move within and the improved recovery when conflict occurs during
evolution means we no longer need to hide hg next triggered evolution behind
a --evolve flag.
It should become the default.
And related change to hg evolve: step by step evolution is an important
feature. However, since hg next will be able to fill this role, is make sense
for hg evolve to evolve all changesets in the current stack by default.
In addition, matching rebase behavior of preserving the working copy parent
seems in order.
These changes will happen in the Evolve extension.
However, after they happen, both hg evolve and hg next should be ready to
be upstreamed provided we have access to a clear definition of the "current
working set" of revisions (as topic provides).
We already have a couple of ways to trigger automatic instability resolution
(eg: next, evolve, …).
However, there could be another good vector to expose it to the user hg
evolve.
The command is already dealing with working copy change and merge conflict.
Adding a hg update --evolve flag could make sense and offer a simple user
experience for some of the simpler case.
Lowering the barrier of entry is always useful.
Instability resolution:
Even if hg evolve can now handle the majority of instability cases, some
remains to be handled.
The unhandled case usually involves a mix of phase-divergence and
content-divergence or some merges, split or fold. We need to hunt down and
handle these remaining cases.
It is probably simpler to tackle the last corner case of automatic
stabilization from the Evolve extension.
So that we can have a wider set of users to test them more quickly.
Besides that, the whole logic is in good shape and ready to be upstreamed.
We can probably start to upstream some of the core bits sooner (eg: upstreaming
hg next would make a good excuse to upstream the orphan resolution).
An alternative approach would be to upstreaming the current instabilities
resolution logic in a way where the Evolve extension can monkey patch fixes
for people using an older version.
This might be more work overall.
User Documentation
There have been inline documentation and tutorials written alongside evolve
development.
However, most of it does not contain the latest commands and workflow. Help is
welcome to refresh them.
Conclusion
I'm happy with the progress made in the past years.
As many, I wished we could have done more, faster, but I'm very excited to have
a clear view on project completion now.
By project completion, I mean mercurial Core to contain a good enough subset of
Changeset Evolution so it could be enabled by default.
At Octobus, we do our best to bring this to completion and mobilize people and
resource to reach this goal.
Next, our own effort will focus on getting the fundations concept in Core:
rewind command, automated resolution of instabilities and efficient obsmarkers
exchange.
In parallel, we'll take care of the supporting concept necessary to safely
enable Changeset Evolution to all users (obs-history viewing, supporting
command, stack and workflow, …).
Of course, this effort is not just performed by people at Octobus or people
working closely with us.
Other Mercurial contributors are also working on their own to complete this project.
What they will exactly do and in what orders is something for them to decide.
All sort of help is welcome.
For multiple years now we have helped the project moved in many ways: through
direct contributions of course, but also by training new people to contribute to
the concept and finally by efficiently gathering and spending money to make the
concept move forward, reaching out, funding, and steering other members of our
open source community to make the project move forward.
Reach out to us if you want to contribute time or money to see Changeset
Evolution enabled by default in Mercurial.
Discussions around the Changeset Evolution concept usually happens on the
#hg-evolve IRC channel on freenode.
If you are using the Evolve extension, do not forget to subscribe to the user list,
Evolve-testers@mercurial-scm.org.
