"rejecting merge with 2 parents" and other inconsistencies when pushing complex history

[RalfJung]

This started as a comment in a PR, but seems worth tracking separately: when pushing Miri history to rustc, I am encountering "rejecting merge with 2 parents". The first example of this occured when pushing Miri (subrepo) commit ff0f5b39d27aaabdcd30bdb3c540583b19a05354 to Rust (monorepo) commit b1ab3b738ac718da74cd4aa0bb7f362d0adbdf84.

I worked around this with a hack, and also supplied a testcase reproducing the problem.

@christian-schilling suggested a better alternative to the hack, however that did not help for the Miri case -- looks like the history there is still more complex than in the testcase.

Meanwhile, the merge created with my hack has been merged into the Rust repo, and I am attempting the next push, which again leads to the same error:

remote: response from upstream:
remote: rejecting merge with 2 parents:
remote: "Auto merge of #2618 - RalfJung:rustup, r=RalfJung"
remote: 1) "Auto merge of #2616 - RalfJung:rustup, r=RalfJung"
remote: 2) "bless clippy"

This is when pushing Miri commit 9d38f807447053ba666220e86305ac4123da905b to Rust commit d49e7e7fa13479c11a3733824c78e280e391288b. And unfortunately, this time my hack does not work -- it creates a totally bogus result with huge diffs to regular rustc master when being merged.

[RalfJung]

Using a different version of the hack seems to result in a sensible history, but this is obviously not a great solution.

[christian-schilling]

So I was looking at the commit graphs of the test case as well as rust and miri and trying to come up with a general algorithm to select a commit. I noticed that my ideas where very similar to what git does when performing a merge (find common ancestor, figure out what side takes priority...)
Thinking of it, it makes some sense to me to attempt a merge at this point. It already covers the case found in the test (the previous solution can be removed) and should work on the current rust/miri situation.
If we run into this again I would consider adding some possibility to manually pick a side (via passing some extra -o)
I updated #994

[RalfJung]

I can confirm that #994 can handle both of the Miri situations I encountered. For the first it ends up creating a commit with the same content as what we ended up merging, but with a different hash -- probably it picked the other (the 2nd) parent. For the second it ends up with exactly the same as my hack that picks the 2nd parent.

[RalfJung]

With #965 and #994 merged, I tried Miri pulling and pushing with latest josh master again, and I am still seeing this problem:

remote: rejecting merge with 2 parents:
remote: "Merge from rustc"
remote: 1) "Auto merge of #2657 - mkroening:miri-alloc, r=RalfJung"
remote: 2) "Auto merge of #104418 - matthiaskrgr:rollup-y4i6xjc, r=matthiaskrgr"

That was trying to push Miri commit 15e7b5a7c314ba7319dba0fb6524a7eefe4a9de4 to rustc commit 6d651a295e0e0c331153288b10b78344a4ede20b.

[RalfJung]

That push is an interesting one since the last time I pulled was the first time I got conflicts when pulling -- so this is the first time pushing after there were conflicts. Possibly that is why it does not work. But I have resolved the conflicts locally in Miri so I expected that would be enough to be able to push things back up.

[RalfJung]

Uh, something else is going on that I don't understand... the branch josh creates doesn't have the base commit it should.

I tried pushing miri as it was before merging the conflict.
I set up master to be rustc 101e1822c3e54e63996c8aaa014d55716f3937eb. miri does not exist. Then I push to josh

JOSH_FILTER=":rev(75dd959a3a40eb5b4574f8d2e23aa6efbeb33573:prefix=src/tools/miri):/src/tools/miri"
git push http://localhost:8000/RalfJung/rust.git$JOSH_FILTER.git HEAD:miri -o base=master

where HEAD is 1e8e0bd83767768fee6b79f8210d5d13ef05ad2b.

But the branch it creates is not based on 101e1822c3e54e63996c8aaa014d55716f3937eb! It is based on something older but includes a few of the more recent commits as well, leading github to display strange diffs in the MR. git merge-base says the branch point is 11fa0850f03ae49fe1053a21bcdcf8a301668ad8.

If I set the miri branch to rustc commit 101e1822c3e54e63996c8aaa014d55716f3937eb and try to push Miri to it, it complains:

remote: josh-proxy
remote: response from upstream:
remote: To github.com:RalfJung/rust.git
remote:  ! [rejected]                JOSH_PUSH -> miri (non-fast-forward)

Not sure why josh produces a history that is not derived from the commit it is supposed to use as base... that's a bug, isn't it? (Looks like the commit it wanted to push is 6759086018f4175cdfc0b9639ab7f8d694a9b289, which is at least consistent with the -o base variant of this. I guess "push to branch with commit X" and "push to new branch, set base to commit X" are in fact equivalent, except that the former will sometimes error due to a force push -- I saw the failing push in the past but did not realize that it created a history based on the wrong base commit.)

The result doesn't even merge cleanly into rustc master, so it's not really usable. So I guess that is to be expected, somewhat, since there are merge conflicts? Not sure what the expected way is to deal with them on a push...

EDIT: This seems to be extremely sensitive to the commit I pick as the base when pushing. If I pick exactly the one I pulled from last time, things seem to work much better.

EDIT2: Ah no that was pure luck it seems. Pulling and then pushing again leads to problems again. Josh seems to prefer if we push a lot, but one motivation for using separate subrepos to begin with is not to have to run full Rust CI for each Miri change -- so we'd rather batch changes for a week or two and then push. Or maybe Josh just doesn't like when we pull twice without a push in between. But that also happens fairly naturally -- we want to usually pull almost immediately when anything changes, which happens fairly regularly as small things need to be fixed in Miri when making a larger rustc change.

[christian-schilling]

This rabbit hole is getting deeper and deeper 🙈
I will need some time to figure this out.

[RalfJung]

Something even worse is wrong -- we're not having proper round-trips any more. :/ When I pull Miri from rustc, I am getting different commit IDs for commits that I recently synced from Miri to rustc. For example "remove a stray stderr file" started out as rust-lang/miri@6140874 in Miri, became rust-lang/rust@46d0df4 in rustc, and returned to Miri as RalfJung/miri@5385e20. And wtf, the version in rustc has a change to the rust-version file? Where is that coming from??

What I am usually doing for rustc-to-miri merges is

• fetch from josh
• merge that into Miri master
• add a rust-version file change to that same merge commit

Maybe josh/git doesn't like that? I could make this a separate commit in the future, I guess.
You also mentioned something about excluding that file, but we want the file to be present in Miri... I guess we could exclude it only when pushing? Seems bad to use a different filter for pulling and pushing though?

Sadly I cannot test if after resolving these conflicts once, things will work in the future... if I try to push to the commit I just pulled from, I get the ol' error again

remote: rejecting merge with 2 parents:
remote: "Merge from rustc"
remote: 1) "Auto merge of #2657 - mkroening:miri-alloc, r=RalfJung"
remote: 2) "Compare picks via `Self` type and associated item id"

I don't have the time to debug something every single pull/push... so I am beginning to wonder if josh might just not be ready yet for our needs. :/

[RalfJung]

Yeah this seems related to having rust-version file changes in the "merge from rustc" commits. When such a commit gets pushed to rustc, josh is confused and ends up creating a commit that does not change the rust-version file. Then some later commit gets the rust-version file change that got missed. And then all children of these get duplicated on the next sync back.

I will stop putting the rust-version file changes into the merge commit, but this makes me worried about what happens for other non-trivial merge commit situations (namely when there are conflicts).

Also, it seems like our history is just permanently broken at this point? I hacked josh to make the push work, but it still cannot round-trip the history after that. Will we get commit duplication on every single rustc-to-Miri pull?

[RalfJung]

Okay I think I understood at least some of what happened... there's a problem with #994. That assumes that if the merge is clean, the result of that merge is the content of the merged commit. But that is not a valid assumption -- Miri commit 218f60ec34004f9fd2d3de95d3d8ead28ad1ea68 is a clean merge but also changes the rust-version file. So when that commit got pushed to rustc, it lost that change, and now the rustc version of Miri's history is just broken...

I'll avoid creating more of these merge commit with further changes in them, but of course that's not a guarantee... #994 should probably be reverted.

[christian-schilling]

I don't have the time to debug something every single pull/push... so I am beginning to wonder if josh might just not be ready yet for our needs. :/

Sorry for that 😒
You are really stretching the scope of what the "push path" has been used for so far. It also makes me wonder if for such a use case it would be better for both directions to be a pull. That would be more like how subtree works. The disadvantage would be that the commits that are authored in miri would not have their tree "augmented" to be a full rust tree and only the merge commits would have a full tree. 🤔

In any case we are looking into this today, still hoping to figure out how to do the push route correctly. And you are right #994 is not correct in it's current form.

[christian-schilling]

Just realized the "pull in both directions" will cause commit duplication: Changes made in rust have full tree and then after a round trip only have partial tree. So that's not really a solution either.

About the "josh might be not ready (yet)" for that use case: What would the alternative(s) be? Giving up on syncing with full history?

[RalfJung]

Yeah I guess we are stress-testing josh with some very complicated histories, aren't we. 😂 Thanks for looking into that!

What would the alternative(s) be? Giving up on syncing with full history?

Yeah. Some home-brew stuff where we remember the last rustc commit we pulled from and the Miri commit that got pulled into, and then a new pull would just create one new commit with all rustc changes, have that Miri commit as parent, and then merge with Miri head. And for the backwards direction we don't even need a merge then if we only ever push right after a pull.

The other tools in rustc use git subtree but Miri's history is too complicated for that.^^

I added some guards to our rustc-push helper to double-check that the created push round-trips properly. Maybe #994 was the source of all our problems? We'll see. We'll do one more force-push in Miri to erase 218f60ec34004f9fd2d3de95d3d8ead28ad1ea68 from our history and replace it with what it becomes after a josh round-trip. Next time something like this happens we'll probably just give up I guess.

Certainly everything I reported above starting here involved the bad 218f60ec34004f9fd2d3de95d3d8ead28ad1ea68. I am pretty sure I saw the behavior of "push picking a strange base and then failing due to having to do a force push" before, but now that we have tracking of which commit to base this on (instead of always pushing to latest rustc master) I think this should also be simpler.

[christian-schilling]

You certainly do and we (as well as future users) will benefit a lot from this. So thanks for your patience so far 🙏🏻

I did figure out what the problem with #994 is: It's just plain wrong. It discards any changes in the merge commit that are not present in the parents.
Doing a merge here is OK, but then the result is a new "base tree" that still needs to be updated with the files from the actual commit. I have fixed the code (locally) but still need to create a proper test case for this.

I'm also thinking about adding the "round trip check" to Josh itself, but it requires some extra thought because we have use cases where we don't want it.

What remains is that there is still a case left that will lead to the "rejecting merge" message. Maybe you only got there as a consequence of the broken #994 but I still want to close that gap somehow 🤔

[RalfJung]

What also remains is that sometimes when I push to a branch, josh creates a commit that is not a descendant of this branch -- so when josh then pushes that to github, it is rejected for being a force-push. That is a bug, right?

[christian-schilling]

What also remains is that sometimes when I push to a branch, josh creates a commit that is not a descendant of this branch -- so when josh then pushes that to github, it is rejected for being a force-push. That is a bug, right?

Yes, I agree. Thats a bug.

[RalfJung]

Okay. If I see it again without the bad merge commits from #994 I'll open an issue with the commit IDs. (The ones I noted above did involve the bad merge, but I am pretty sure I've seen this earlier, too. But maybe that was due to my hack for working around the "rejecting merge" issue...)

[christian-schilling]

Thanks, that will help 🙏

The bad merge problem is fixed in #1044

[RalfJung]

We didn't have trouble for a while, but now trouble is back: we had a conflict when doing a sync from rustc to miri (monorepo to subrepo), which I resolved by hand. Now trying to push Miri to rustc fails:

remote: Resolving deltas: 100% (248/248), completed with 99 local objects.
remote: josh-proxy
remote: response from upstream:
remote: rejecting merge with 2 parents:
remote: "Merge from rustc"
remote: 1) "Preparing for merge from rustc"
remote: 2) "cmp doc examples consistency improvements"

Not sure yet how to work around this, this currently blocks our ability to ship an updated Miri to users.

I am not entirely sure which version of josh this is (josh-proxy -v/-V/--version don't seem to be a thing); the cargo crates tracking indicates v22.4.15.

EDIT: Oh that was the Cargo.toml version number; 22.12.06 is what I actually had installed.

[RalfJung]

Seems like at least the old hack still works

diff --git a/src/history.rs b/src/history.rs
index 5e66584..aeecca4 100644
--- a/src/history.rs
+++ b/src/history.rs
@@ -482,17 +482,8 @@ pub fn unapply_filter(
                 }
 
                 if tid == git2::Oid::zero() {
-                    // We give up. If we see this message again we need to investigate once
-                    // more and maybe consider allowing a manual override as last resort.
-                    tracing::warn!("rejecting merge");
-                    let msg = format!(
-                        "rejecting merge with {} parents:\n{:?}\n1) {:?}\n2) {:?}",
-                        parent_count,
-                        module_commit.summary().unwrap_or_default(),
-                        original_parents_refs[0].summary().unwrap_or_default(),
-                        original_parents_refs[1].summary().unwrap_or_default(),
-                    );
-                    return Err(josh_error(&msg));
+                    // HACK HACK HACK
+                    tid = new_trees[0];
                 }
 
                 transaction.repo().find_tree(tid)?

The resulting history does round-trip properly, so I hope it's going to be fine.

[RalfJung]

Another reproducer:

• cargo +stable install josh-proxy --git https://github.com/josh-project/josh --tag r22.12.06 (same result with --tag r23.02.14)
• josh-proxy --local ~/.cache/miri-josh/ --remote https://github.com --no-background
• (in a rustc checkout) git push https://github.com/RalfJung/rust.git a989e25f1b87949a886eab3da10324d14189fe95:refs/heads/miri
• (in a Miri checkout) git push 'http://localhost:8000/RalfJung/rust.git:rev(75dd959a3a40eb5b4574f8d2e23aa6efbeb33573:prefix=src/tools/miri):/src/tools/miri.git' 4f5d9517a315ea06e27f3bbbcb17cdb2b92333b2:miri

remote: josh-proxy
remote: response from upstream:
remote: rejecting merge with 2 parents:
remote: "Merge from rustc"
remote: 1) "Preparing for merge from rustc"
remote: 2) "Auto merge of #115276 - fmease:rustdoc-obj-lt-defs-handle-self-ty-params, r=GuillaumeGomez"
remote: 
remote: 
remote: error: hook declined to update refs/heads/miri

Again this was after we had a conflict when pulling changes from rusts to Miri. We don't get this on all conflicts though.

[RalfJung]

@christian-schilling do you have any suggestions for how to proceed here? Currently I am using my patch to work around the problem, but I am also cautioning other parts of the Rust project against using josh-proxy since I have no idea what the underlying issue is and whether there's a risk of larger problems (like one day not being able to do a properly round-tripping push at all).

[christian-schilling]

@RalfJung, thanks for the report.
I did some digging what is happening in this case and found that the atempt to merge the trees fails due to a conflict in
/src/tools/miri/tests/pass/function_calls/abi_compat.rs. This is a file that is part of the to-be-pushed tree and thus we know what it should look like, regardless of what happens during the merge. I changed the approach to handle cases like this in #1279 (also see comment in code) and confirmed with your example that this does indeed work.

Regarding possible larger problems regarding "round trip correctness": I don't think there is a risk here:
The code in question is about finding and selecting a tree for the upstream repo that will result in a history which will round trip correctly. The issues we have been seing are because any of the candidate trees will result in such a usable history and we still need to make a decision on which one to use.
That is also why your "hack" works: Even select one of the options at random would be fine, as all the options result in the same history for the filtered branch. The only difference is in other parts of the tree that are not relevant for the round trip but might be relvant regarding other criteria (like the code being buildable)
So with round trip being guranteed, we still want the rest of the tree to be in a state that makes sense. And in this particular case at least this tree could be constructed but the algorithm was not able to realize that.

[RalfJung]

Thanks for looking into this! I'll update my josh to a dev version once your PR lands, and report back here if/when I see any issues again.

[christian-schilling]

Landed #1279. Sorry for the long wait.

[RalfJung]

No worries! I have now installed that version, and can confirm that the testcase posted above now round-trips properly. It doesn't generate exactly the same commit as my branch did, but that seems fine.

I will report back whether I see any issues in future pushes.