27 KiB
The merge command
The merge command merges together two branches in the same project: the current branch (unspecificed), and the target
branch. For example, to merge topic into main, switch to main and run merge topic:
scratch/main> help merge
scratch/main> help merge.commit
Let's see a simple unconflicted merge in action: Alice (us) and Bob (them) add different terms. The merged result contains both additions.
Basic merge: two unconflicted adds
project/main> builtins.mergeio lib.builtins
project/main> branch alice
Alice's adds:
foo : Text
foo = "alices foo"
project/alice> add
project/main> branch bob
Bob's adds:
bar : Text
bar = "bobs bar"
project/bob> add
Merge result:
project/alice> merge /bob
project/alice> view foo bar
scratch/main> project.delete project
Basic merge: two identical adds
If Alice and Bob also happen to add the same definition, that's not a conflict.
project/main> builtins.mergeio lib.builtins
project/main> branch alice
Alice's adds:
foo : Text
foo = "alice and bobs foo"
project/alice> add
project/main> branch bob
Bob's adds:
foo : Text
foo = "alice and bobs foo"
bar : Text
bar = "bobs bar"
project/bob> add
Merge result:
project/alice> merge /bob
project/alice> view foo bar
scratch/main> project.delete project
Simple update propagation
Updates that occur in one branch are propagated to the other. In this example, Alice updates foo, while Bob adds a new dependent bar of the original foo. When Bob's branch is merged into Alice's, her update to foo is propagated to his bar.
project/main> builtins.mergeio lib.builtins
Original branch:
foo : Text
foo = "old foo"
project/main> add
project/main> branch alice
Alice's updates:
foo : Text
foo = "new foo"
project/alice> update
project/main> branch bob
Bob's adds:
bar : Text
bar = foo ++ " - " ++ foo
project/bob> display bar
project/bob> add
Merge result:
project/alice> merge /bob
project/alice> view foo bar
project/alice> display bar
scratch/main> project.delete project
Update propagation with common dependent
We classify something as an update if its "syntactic hash"—not its normal Unison hash—differs from the original definition. This allows us to cleanly merge unconflicted updates that were individually propagated to a common dependent.
Let's see an example. We have foo, which depends on bar and baz. Alice updates bar (propagating to foo), and Bob updates baz (propagating to foo). When we merge their updates, both updates will be reflected in the final foo.
project/main> builtins.mergeio lib.builtins
Original branch:
foo : Text
foo = "foo" ++ " - " ++ bar ++ " - " ++ baz
bar : Text
bar = "old bar"
baz : Text
baz = "old baz"
project/main> add
project/main> branch alice
Alice's updates:
bar : Text
bar = "alices bar"
project/alice> update
project/alice> display foo
project/main> branch bob
Bob's updates:
baz : Text
baz = "bobs baz"
project/bob> update
project/bob> display foo
Merge result:
project/alice> merge /bob
project/alice> view foo bar baz
project/alice> display foo
scratch/main> project.delete project
Propagating an update to an update
Of course, it's also possible for Alice's update to propagate to one of Bob's updates. In this example, foo depends on bar which depends on baz. Alice updates baz, propagating to bar and foo, while Bob updates bar (to something that still depends on foo), propagating to baz. The merged result will have Alice's update to foo incorporated into Bob's updated bar, and both updates will propagate to baz.
project/main> builtins.mergeio lib.builtins
Original branch:
foo : Text
foo = "old foo" ++ " - " ++ bar
bar : Text
bar = "old bar" ++ " - " ++ baz
baz : Text
baz = "old baz"
project/main> add
project/main> display foo
project/main> branch alice
Alice's updates:
baz : Text
baz = "alices baz"
project/alice> update
project/alice> display foo
project/main> branch bob
Bob's updates:
bar : Text
bar = "bobs bar" ++ " - " ++ baz
project/bob> update
project/bob> display foo
Merge result:
project/alice> merge /bob
project/alice> view foo bar baz
project/alice> display foo
scratch/main> project.delete project
Update + delete isn't (currently) a conflict
We don't currently consider "update + delete" a conflict like Git does. In this situation, the delete is just ignored, allowing the update to proceed.
project/main> builtins.mergeio lib.builtins
Original branch:
foo : Text
foo = "old foo"
project/main> add
project/main> branch alice
Alice's updates:
foo : Text
foo = "alices foo"
project/alice> update
project/main> branch bob
Bob's changes:
project/bob> delete.term foo
Merge result:
project/alice> merge /bob
project/alice> view foo
scratch/main> project.delete project
In a future version, we'd like to give the user a warning at least.
Library dependencies don't create merge conflicts
Library dependencies don't cause merge conflicts, the library dependencies are just unioned together. If two library dependencies have the same name but different namespace hashes, then the merge algorithm makes up two fresh names.
project/main> builtins.mergeio lib.builtins
Alice's adds:
project/main> branch alice
lib.alice.foo : Nat
lib.alice.foo = 17
lib.bothSame.bar : Nat
lib.bothSame.bar = 18
lib.bothDifferent.baz : Nat
lib.bothDifferent.baz = 19
project/alice> add
project/main> branch bob
Bob's adds:
lib.bob.foo : Nat
lib.bob.foo = 20
lib.bothSame.bar : Nat
lib.bothSame.bar = 18
lib.bothDifferent.baz : Nat
lib.bothDifferent.baz = 21
project/bob> add
Merge result:
project/alice> merge bob
project/alice> view foo bar baz
scratch/main> project.delete project
No-op merge (Bob = Alice)
If Bob is equals Alice, then merging Bob into Alice looks like this.
project/main> builtins.mergeio lib.builtins
project/main> branch alice
project/main> branch bob
project/alice> merge /bob
scratch/main> project.delete project
No-op merge (Bob < Alice)
If Bob is behind Alice, then merging Bob into Alice looks like this.
project/main> builtins.mergeio lib.builtins
project/main> branch alice
project/main> branch bob
Alice's addition:
foo : Text
foo = "foo"
project/alice> add
project/alice> merge /bob
scratch/main> project.delete project
Fast-forward merge (Bob > Alice)
If Bob is ahead of Alice, then merging Bob into Alice looks like this.
project/main> builtins.mergeio lib.builtins
project/main> branch alice
project/main> branch bob
Bob's addition:
foo : Text
foo = "foo"
project/bob> add
project/alice> merge /bob
scratch/main> project.delete project
No-op merge: merge empty namespace into empty namespace
project/main> branch topic
project/main> merge /topic
scratch/main> project.delete project
Merge failure: someone deleted something
If either Alice or Bob delete something, so long as the other person didn't update it (in which case we ignore the delete, as explained above), then the delete goes through.
This can cause merge failures due to out-of-scope identifiers, and the user may have to do some digging around to find what the deleted name used to refer to. In a future version, we would emit a [better] warning at least.
In this example, Alice deletes foo, while Bob adds a new dependent of foo.
project/main> builtins.mergeio lib.builtins
Original branch:
foo : Text
foo = "foo"
project/main> add
project/main> branch alice
Alice's delete:
project/alice> delete.term foo
project/main> branch bob
Bob's new code that depends on foo:
bar : Text
bar = foo ++ " - " ++ foo
project/bob> add
project/alice> merge /bob
scratch/main> project.delete project
Merge failure: type error
It may be Alice's and Bob's changes merge together cleanly in the sense that there's no textual conflicts, yet the resulting namespace doesn't typecheck.
In this example, Alice updates a Text to a Nat, while Bob adds a new dependent of the Text. Upon merging, propagating Alice's update to Bob's dependent causes a typechecking failure.
project/main> builtins.mergeio lib.builtins
Original branch:
foo : Text
foo = "foo"
project/main> add
project/main> branch alice
Alice's update:
foo : Nat
foo = 100
project/alice> update
project/main> branch bob
Bob's new definition:
bar : Text
bar = foo ++ " - " ++ foo
project/bob> update
project/alice> merge /bob
scratch/main> project.delete project
Merge failure: simple term conflict
Alice and Bob may disagree about the definition of a term. In this case, the conflicted term and all of its dependents are presented to the user to resolve.
project/main> builtins.mergeio lib.builtins
Original branch:
foo : Text
foo = "old foo"
bar : Text
bar = "old bar"
project/main> add
project/main> branch alice
Alice's changes:
foo : Text
foo = "alices foo"
bar : Text
bar = "alices bar"
qux : Text
qux = "alices qux depends on alices foo" ++ foo
project/alice> update
project/main> branch bob
Bob's changes:
foo : Text
foo = "bobs foo"
baz : Text
baz = "bobs baz"
project/bob> update
project/alice> merge /bob
project/merge-bob-into-alice> view bar baz
scratch/main> project.delete project
Merge failure: simple type conflict
Ditto for types; if the hashes don't match, it's a conflict. In this example, Alice and Bob do different things to the same constructor. However, any explicit changes to the same type will result in a conflict, including changes that could concievably be merged (e.g. Alice and Bob both add a new constructor, or edit different constructors).
project/main> builtins.mergeio lib.builtins
Original branch:
unique type Foo = MkFoo Nat
project/main> add
project/main> branch alice
Alice's changes:
unique type Foo = MkFoo Nat Nat
project/alice> update
project/main> branch bob
Bob's changes:
unique type Foo = MkFoo Nat Text
project/bob> update
project/alice> merge /bob
scratch/main> project.delete project
Merge failure: type-update + constructor-rename conflict
We model the renaming of a type's constructor as an update, so if Alice updates a type and Bob renames one of its constructors (even without changing its structure), we consider it a conflict.
project/main> builtins.mergeio lib.builtins
Original branch:
unique type Foo = Baz Nat | Qux Text
project/main> add
project/main> branch alice
Alice's changes Baz Nat to Baz Nat Nat
unique type Foo = Baz Nat Nat | Qux Text
project/alice> update
project/main> branch bob
Bob's renames Qux to BobQux:
project/bob> move.term Foo.Qux Foo.BobQux
project/alice> merge /bob
scratch/main> project.delete project
Merge failure: constructor-rename conflict
Here is another example demonstrating that constructor renames are modeled as updates.
project/main> builtins.mergeio lib.builtins
Original branch:
unique type Foo = Baz Nat | Qux Text
project/main> add
project/main> branch alice
Alice's rename:
project/alice> move.term Foo.Baz Foo.Alice
project/main> branch bob
Bob's rename:
project/bob> move.term Foo.Qux Foo.Bob
project/alice> merge bob
scratch/main> project.delete project
Merge failure: non-constructor/constructor conflict
A constructor on one side can conflict with a regular term definition on the other.
project/main> builtins.mergeio lib.builtins
project/main> branch alice
Alice's additions:
my.cool.thing : Nat
my.cool.thing = 17
project/alice> add
project/main> branch bob
Bob's additions:
unique ability my.cool where
thing : Nat -> Nat
project/bob> add
project/alice> merge bob
scratch/main> project.delete project
Merge failure: type/type conflict with term/constructor conflict
Here's a subtle situation where a new type is added on each side of the merge, and an existing term is replaced with a constructor of one of the types.
project/main> builtins.mergeio lib.builtins
Original branch:
Foo.Bar : Nat
Foo.Bar = 17
project/main> add
project/main> branch alice
Alice adds this type Foo with constructor Foo.Alice:
unique type Foo = Alice Nat
project/alice> add
project/main> branch bob
Bob adds the type Foo with constructor Foo.Bar, replacing the original Foo.Bar term:
project/bob> delete.term Foo.Bar
unique type Foo = Bar Nat Nat
project/bob> add
These won't cleanly merge.
project/alice> merge bob
scratch/main> project.delete project
Here's a more involved example that demonstrates the same idea.
project/main> builtins.mergeio lib.builtins
In the LCA, we have a type with two constructors, and some term.
unique type Foo
= Bar.Baz Nat
| Bar.Qux Nat Nat
Foo.Bar.Hello : Nat
Foo.Bar.Hello = 17
project/main> add
project/main> branch alice
Alice deletes this type entirely, and repurposes its constructor names for other terms. She also updates the term.
project/alice> delete.type Foo
project/alice> delete.term Foo.Bar.Baz
project/alice> delete.term Foo.Bar.Qux
Foo.Bar.Baz : Nat
Foo.Bar.Baz = 100
Foo.Bar.Qux : Nat
Foo.Bar.Qux = 200
Foo.Bar.Hello : Nat
Foo.Bar.Hello = 18
project/alice> update
project/alice> view Foo.Bar.Baz Foo.Bar.Qux Foo.Bar.Hello
Bob, meanwhile, first deletes the term, then sort of deletes the type and re-adds it under another name, but one constructor's fully qualified names doesn't actually change. The other constructor reuses the name of the deleted term.
project/main> branch bob
project/bob> delete.term Foo.Bar.Hello
project/bob> move.type Foo Foo.Bar
project/bob> move.term Foo.Bar.Qux Foo.Bar.Hello
project/bob> view Foo.Bar
At this point, Bob and alice have both updated the name Foo.Bar.Hello in different ways, so that's a conflict. Therefore, Bob's entire type (Foo.Bar with constructors Foo.Bar.Baz and Foo.Bar.Hello) gets rendered into the scratch file.
Notably, Alice's "unconflicted" update on the name "Foo.Bar.Baz" (because she changed its hash and Bob didn't touch it) is nonetheless considered conflicted with Bob's "Foo.Bar.Baz".
project/alice> merge bob
scratch/main> project.delete project
Merge algorithm quirk: add/add unique types
Currently, two unique types created by Alice and Bob will be considered in conflict, even if they "look the same". The result may be confusing to a user – a file containing two identical-looking copies of a unique type is rendered, which is a parse error.
We will resolve this situation automatically in a future version.
project/main> builtins.mergeio lib.builtins
project/main> branch alice
Alice's additions:
unique type Foo = Bar
alice : Foo -> Nat
alice _ = 18
project/alice> add
project/main> branch bob
Bob's additions:
unique type Foo = Bar
bob : Foo -> Nat
bob _ = 19
project/bob> add
project/alice> merge bob
scratch/main> project.delete project
merge.commit example (success)
After merge conflicts are resolved, you can use merge.commit rather than switch + merge + branch.delete to
"commit" your changes.
project/main> builtins.mergeio lib.builtins
Original branch:
foo : Text
foo = "old foo"
project/main> add
project/main> branch alice
Alice's changes:
foo : Text
foo = "alices foo"
project/alice> update
project/main> branch bob
Bob's changes:
foo : Text
foo = "bobs foo"
Attempt to merge:
project/bob> update
project/alice> merge /bob
Resolve conflicts and commit:
foo : Text
foo = "alice and bobs foo"
project/merge-bob-into-alice> update
project/merge-bob-into-alice> merge.commit
project/alice> view foo
project/alice> branches
scratch/main> project.delete project
merge.commit example (failure)
merge.commit can only be run on a "merge branch".
project/main> builtins.mergeio lib.builtins
project/main> branch topic
project/topic> merge.commit
scratch/main> project.delete project
Precondition violations
There are a number of conditions under which we can't perform a merge, and the user will have to fix up the namespace(s) manually before attempting to merge again.
Conflicted aliases
If foo and bar are aliases in the nearest common ancestor, but not in Alice's branch, then we don't know whether to update Bob's dependents to Alice's foo or Alice's bar (and vice-versa).
project/main> builtins.mergeio lib.builtins
Original branch:
foo : Nat
foo = 100
bar : Nat
bar = 100
project/main> add
project/main> branch alice
Alice's updates:
foo : Nat
foo = 200
bar : Nat
bar = 300
project/alice> update
project/main> branch bob
Bob's addition:
baz : Text
baz = "baz"
project/bob> add
project/alice> merge /bob
scratch/main> project.delete project
Conflict involving builtin
We don't have a way of rendering a builtin in a scratch file, where users resolve merge conflicts. Thus, if there is a conflict involving a builtin, we can't perform a merge.
One way to fix this in the future would be to introduce a syntax for defining aliases in the scratch file.
project/main> builtins.mergeio lib.builtins
project/main> branch alice
Alice's branch:
project/alice> alias.type lib.builtins.Nat MyNat
Bob's branch:
project/main> branch bob
unique type MyNat = MyNat Nat
project/bob> add
project/alice> merge /bob
scratch/main> project.delete project
Constructor alias
Each naming of a decl may not have more than one name for each constructor, within the decl's namespace.
project/main> builtins.mergeio lib.builtins
project/main> branch alice
Alice's branch:
unique type Foo = Bar
project/alice> add
project/alice> alias.term Foo.Bar Foo.some.other.Alias
Bob's branch:
project/main> branch bob
bob : Nat
bob = 100
project/bob> add
project/alice> merge /bob
scratch/main> project.delete project
Missing constructor name
Each naming of a decl must have a name for each constructor, within the decl's namespace.
project/main> builtins.mergeio lib.builtins
Alice's branch:
project/main> branch alice
unique type Foo = Bar
project/alice> add
project/alice> delete.term Foo.Bar
Bob's branch:
project/main> branch /bob
bob : Nat
bob = 100
project/bob> add
project/alice> merge /bob
scratch/main> project.delete project
Nested decl alias
A decl cannot be aliased within the namespace of another of its aliased.
project/main> builtins.mergeio lib.builtins
Alice's branch:
project/main> branch alice
structural type A = B Nat | C Nat Nat
structural type A.inner.X = Y Nat | Z Nat Nat
project/alice> add
project/alice> names A
Bob's branch:
project/main> branch bob
bob : Nat
bob = 100
project/bob> add
project/alice> merge /bob
scratch/main> project.delete project
Stray constructor alias
Constructors may only exist within the corresponding decl's namespace.
project/main> builtins.mergeio lib.builtins
Alice's branch:
project/main> branch alice
unique type Foo = Bar
project/alice> add
project/alice> alias.term Foo.Bar AliasOutsideFooNamespace
Bob's branch:
project/main> branch bob
bob : Nat
bob = 101
project/bob> add
project/alice> merge bob
scratch/main> project.delete project
Term or type in lib
By convention, lib can only namespaces; each of these represents a library dependencies. Individual terms and types are not allowed at the top level of lib.
project/main> builtins.mergeio lib.builtins
Alice's branch:
project/main> branch alice
lib.foo : Nat
lib.foo = 1
project/alice> add
project/main> branch bob
Bob's branch:
bob : Nat
bob = 100
project/bob> add
project/alice> merge /bob
scratch/main> project.delete project
LCA precondition violations
The LCA is not subject to most precondition violations, which is good, because the user can't easily manipulate it!
Here's an example. We'll delete a constructor name from the LCA and still be able to merge Alice and Bob's stuff together.
project/main> builtins.mergeio lib.builtins
LCA:
structural type Foo = Bar Nat | Baz Nat Nat
project/main> add
project/main> delete.term Foo.Baz
Alice's branch:
project/main> branch alice
project/alice> delete.type Foo
project/alice> delete.term Foo.Bar
alice : Nat
alice = 100
project/alice> add
Bob's branch:
project/main> branch bob
project/bob> delete.type Foo
project/bob> delete.term Foo.Bar
bob : Nat
bob = 101
project/bob> add
Now we merge:
project/alice> merge /bob
scratch/main> project.delete project
Regression tests
Delete one alias and update the other
project/main> builtins.mergeio lib.builtins
foo = 17
bar = 17
project/main> add
project/main> branch alice
project/alice> delete.term bar
foo = 18
project/alice> update
project/main> branch bob
bob = 101
project/bob> add
project/alice> merge /bob
scratch/main> project.delete project
Delete a constructor
project/main> builtins.mergeio lib.builtins
type Foo = Bar | Baz
project/main> add
project/main> branch topic
boop = "boop"
project/topic> add
type Foo = Bar
project/main> update
project/main> merge topic
project/main> view Foo
scratch/main> project.delete project
Dependent that doesn't need to be in the file
This test demonstrates a bug.
project/alice> builtins.mergeio lib.builtins
In the LCA, we have foo with dependent bar, and baz.
foo : Nat
foo = 17
bar : Nat
bar = foo + foo
baz : Text
baz = "lca"
project/alice> add
project/alice> branch bob
On Bob, we update baz to "bob".
baz : Text
baz = "bob"
project/bob> update
On Alice, we update baz to "alice" (conflict), but also update foo (unconflicted), which propagates to bar.
foo : Nat
foo = 18
baz : Text
baz = "alice"
project/alice> update
When we try to merge Bob into Alice, we should see both versions of baz, with Alice's unconflicted foo and bar in
the underlying namespace.
project/alice> merge /bob
But bar was put into the scratch file instead.
scratch/main> project.delete project
Merge loop test
This tests for regressions of https://github.com/unisonweb/unison/issues/1276 where trivial merges cause loops in the history.
Let's make three identical namespaces with different histories:
a = 1
project/alice> add
b = 2
project/alice> add
b = 2
project/bob> add
a = 1
project/bob> add
a = 1
b = 2
project/carol> add
project/bob> merge /alice
project/carol> merge /bob
project/carol> history
scratch/main> project.delete project
Variables named _
This test demonstrates a change in syntactic hashing that fixed a bug due to auto-generated variable names for ignored results.
scratch/alice> builtins.mergeio lib.builtins
ignore : a -> ()
ignore _ = ()
foo : Nat
foo = 18
bar : Nat
bar =
ignore "hi"
foo + foo
scratch/alice> add
scratch/alice> branch bob
bar : Nat
bar =
ignore "hi"
foo + foo + foo
scratch/bob> update
Previously, this update to foo would also cause a "real update" on bar, its dependent. Now it doesn't, so the merge
will succeed.
foo : Nat
foo = 19
scratch/alice> update
scratch/alice> merge /bob