From: Thomas Gummerer <t.gummerer@gmail.com>
To: Junio C Hamano <gitster@pobox.com>
Cc: git@vger.kernel.org
Subject: Re: [RFC/PATCH 3/7] rerere: add some documentation
Date: Sun, 3 Jun 2018 12:41:28 +0100 [thread overview]
Message-ID: <20180603114128.GD18193@hank.intra.tgummerer.com> (raw)
In-Reply-To: <xmqqr2m1quja.fsf@gitster-ct.c.googlers.com>
On 05/24, Junio C Hamano wrote:
> Thomas Gummerer <t.gummerer@gmail.com> writes:
>
> > +Conflict normalization
> > +----------------------
> > +
> > +To try and re-do a conflict resolution, even when different merge
> > +strategies are used, 'rerere' computes a conflict ID for each
> > +conflict in the file.
> > +
> > +This is done by discarding the common ancestor version in the
> > +diff3-style, and re-ordering the two sides of the conflict, in
> > +alphabetic order.
>
> s/discarding.*-style/normalising the conflicted section to 'merge' style/
>
> The motivation behind the normalization should probably be given
> upfront in the first paragraph. It is to ensure the recorded
> resolutions can be looked up from the rerere database for
> application, even when branches are merged in different order. I am
> not sure what you meant by even when different merge stratagies are
> used; I'd drop that if I were writing the paragraph.
What I meant was when different conflict styles are used, and when the
branches are merged in different orders. But merge strategies is
obviously not a good word for that. Will rephrase this.
> > +Using this technique a conflict that looks as follows when for example
> > +'master' was merged into a topic branch:
> > +
> > + <<<<<<< HEAD
> > + foo
> > + =======
> > + bar
> > + >>>>>>> master
> > +
> > +and the opposite way when the topic branch is merged into 'master':
> > +
> > + <<<<<<< HEAD
> > + bar
> > + =======
> > + foo
> > + >>>>>>> topic
> > +
> > +can be recognized as the same conflict, and can automatically be
> > +re-resolved by 'rerere', as the SHA-1 sum of the two conflicts would
> > +be calculated from 'bar<NUL>foo<NUL>' in both cases.
>
> You earlier talked about normalizing and reordering, but did not
> talk about "concatenate both with NUL in between and hash", so the
> explanation in the last two lines are not quite understandable by
> mere mortals, even though I know which part of the code you are
> referring to. When you talk about hasing, you may want to make sure
> the readers understand that the branch label on <<< and >>> lines
> are ignored.
>
> > +If there are multiple conflicts in one file, they are all appended to
> > +one another, both in the 'preimage' file as well as in the conflict
> > +ID.
>
> In case it was not clear (and I do not think it is to those who only
> read your description and haven't thought things through
> themselves), this concatenation is why the normalization by
> reordering is helpful. Imagine that a common ancestor had a file
> with a line with string "A" on it (I'll call such a line "line A"
> for brevity in the following) in its early part, and line X in its
> late part. And then you fork four branches that do these things:
>
> - AB: changes A to B
> - AC: changes A to C
> - XY: changes X to Y
> - XZ: changes X to Z
>
> Now, forking a branch ABAC off of branch AB and then merging AC into
> it, and forking a branch ACAB off of branch AC and then merging AB
> into it, would yield the conflict in a different order. The former
> would say "A became B or C, what now?" while the latter would say "A
> became C or B, what now?"
>
> But the act of merging AC into ABAC and resolving the conflict to
> leave line D means that you declare:
>
> After examining what branches AB and AC did, I believe that
> making line A into line D is the best thing to do that is
> compatible with what AB and AC wanted to do.
>
> So the conflict we would see when merging AB into ACAB should be
> resolved the same way---it is the resolution that is in line with
> that declaration.
>
> Imagine that similarly you had previously forked branch XYXZ from
> XY, merged XZ into it, and resolved "X became Y or Z" into "X became
> W".
>
> Now, if you forked a branch ABXY from AB and then merged XY, then
> ABXY would have line B in its early part and line Y in its later
> part. Such a merge would be quite clean. We can construct
> 4 combinations using these four branches ((AB, AC) x (XY, XZ)).
>
> Merging ABXY and ACXZ would make "an early A became B or C, a late X
> became Y or Z" conflict, while merging ACXY and ABXZ would make "an
> early A became C or B, a late X became Y or Z". We can see there
> are 4 combinations of ("B or C", "C or B") x ("X or Y", "Y or X").
>
> By sorting, we can give the conflict its canonical name, namely, "an
> early part became B or C, a late part becames X or Y", and whenever
> any of these four patterns appear, we can get to the same conflict
> and resolution that we saw earlier. Without the sorting, we will
> have to somehow find a previous resolution from combinatorial
> explosion ;-)
Thanks for the in depth explanation! I'll incorporate this into the
document.
> These days post ec34a8b1 ("Merge branch 'jc/rerere-multi'",
> 2016-05-23), the conflict ID can safely collide, i.e. hash
> collisions that drops completely different conflicts and their
> resolutions into the same .git/rr-cache/$id directory will not
> interfere with proper operation of the system, thanks to that
> rerere-multi topic that allows us to store multiple preimage
> conflicts that happens to share the same conflict ID with their
> corresponding postimage resolutions.
>
> In theory, we *should* be able to stub out the SHA-1 computation and
> give every conflict the same ID and rerere should still operate
> correctly, even though I haven't tried it yet myself.
I gave this a quick try, and the test suite seems to pass with the
hash computation giving the same ID to all conflicts.
next prev parent reply other threads:[~2018-06-03 11:40 UTC|newest]
Thread overview: 84+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-05-20 21:12 [RFC/PATCH 0/7] rerere: handle nested conflicts Thomas Gummerer
2018-05-20 21:12 ` [RFC/PATCH 1/7] rerere: unify error message when read_cache fails Thomas Gummerer
2018-05-21 19:00 ` Stefan Beller
2018-05-20 21:12 ` [RFC/PATCH 2/7] rerere: mark strings for translation Thomas Gummerer
2018-05-24 7:20 ` Junio C Hamano
2018-05-20 21:12 ` [RFC/PATCH 3/7] rerere: add some documentation Thomas Gummerer
2018-05-24 9:20 ` Junio C Hamano
2018-06-03 11:41 ` Thomas Gummerer [this message]
2018-05-20 21:12 ` [RFC/PATCH 4/7] rerere: fix crash when conflict goes unresolved Thomas Gummerer
2018-05-24 9:47 ` Junio C Hamano
2018-05-24 18:54 ` Thomas Gummerer
2018-05-25 1:20 ` Junio C Hamano
2018-05-20 21:12 ` [RFC/PATCH 5/7] rerere: only return whether a path has conflicts or not Thomas Gummerer
2018-05-24 10:02 ` Junio C Hamano
2018-05-20 21:12 ` [RFC/PATCH 6/7] rerere: factor out handle_conflict function Thomas Gummerer
2018-05-20 21:12 ` [RFC/PATCH 7/7] rerere: teach rerere to handle nested conflicts Thomas Gummerer
2018-05-24 10:21 ` Junio C Hamano
2018-05-24 19:07 ` Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 00/10] rerere: " Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 01/10] rerere: unify error messages when read_cache fails Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 02/10] rerere: lowercase error messages Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 03/10] rerere: wrap paths in output in sq Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 04/10] rerere: mark strings for translation Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 05/10] rerere: add some documentation Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 06/10] rerere: fix crash when conflict goes unresolved Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 07/10] rerere: only return whether a path has conflicts or not Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 08/10] rerere: factor out handle_conflict function Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 09/10] rerere: teach rerere to handle nested conflicts Thomas Gummerer
2018-06-05 21:52 ` [PATCH v2 10/10] rerere: recalculate conflict ID when unresolved conflict is committed Thomas Gummerer
2018-07-03 21:05 ` [PATCH v2 00/10] rerere: handle nested conflicts Thomas Gummerer
2018-07-06 17:56 ` Junio C Hamano
2018-07-10 21:37 ` Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 00/11] " Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 01/11] rerere: unify error messages when read_cache fails Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 02/11] rerere: lowercase error messages Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 03/11] rerere: wrap paths in output in sq Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 04/11] rerere: mark strings for translation Thomas Gummerer
2018-07-15 13:24 ` Simon Ruderich
2018-07-16 20:40 ` Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 05/11] rerere: add documentation for conflict normalization Thomas Gummerer
2018-07-30 17:50 ` Junio C Hamano
2018-07-30 20:21 ` Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 06/11] rerere: fix crash when conflict goes unresolved Thomas Gummerer
2018-07-30 17:50 ` Junio C Hamano
2018-07-30 20:45 ` Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 07/11] rerere: only return whether a path has conflicts or not Thomas Gummerer
2018-07-30 17:50 ` Junio C Hamano
2018-07-30 20:47 ` Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 08/11] rerere: factor out handle_conflict function Thomas Gummerer
2018-07-30 17:51 ` Junio C Hamano
2018-07-14 21:44 ` [PATCH v3 09/11] rerere: return strbuf from handle path Thomas Gummerer
2018-07-30 17:51 ` Junio C Hamano
2018-07-14 21:44 ` [PATCH v3 10/11] rerere: teach rerere to handle nested conflicts Thomas Gummerer
2018-07-30 17:45 ` Junio C Hamano
2018-07-30 20:20 ` Thomas Gummerer
2018-07-14 21:44 ` [PATCH v3 11/11] rerere: recalculate conflict ID when unresolved conflict is committed Thomas Gummerer
2018-07-30 17:50 ` [PATCH v3 00/11] rerere: handle nested conflicts Junio C Hamano
2018-07-30 20:49 ` Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 " Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 01/11] rerere: unify error messages when read_cache fails Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 02/11] rerere: lowercase error messages Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 03/11] rerere: wrap paths in output in sq Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 04/11] rerere: mark strings for translation Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 05/11] rerere: add documentation for conflict normalization Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 06/11] rerere: fix crash with files rerere can't handle Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 07/11] rerere: only return whether a path has conflicts or not Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 08/11] rerere: factor out handle_conflict function Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 09/11] rerere: return strbuf from handle path Thomas Gummerer
2018-08-05 17:20 ` [PATCH v4 10/11] rerere: teach rerere to handle nested conflicts Thomas Gummerer
2018-08-22 11:00 ` Ævar Arnfjörð Bjarmason
2018-08-22 16:06 ` Junio C Hamano
2018-08-22 20:34 ` Thomas Gummerer
2018-08-22 21:07 ` Junio C Hamano
2018-08-24 21:56 ` Thomas Gummerer
2018-08-24 22:10 ` [PATCH 1/2] rerere: remove documentation for "nested conflicts" Thomas Gummerer
2018-08-24 22:10 ` [PATCH 2/2] rerere: add not about files with existing conflict markers Thomas Gummerer
2018-08-28 21:27 ` [PATCH v2 1/2] rerere: mention caveat about unmatched " Thomas Gummerer
2018-08-28 21:27 ` [PATCH v2 2/2] rerere: add note about files with existing " Thomas Gummerer
2018-08-29 16:04 ` [PATCH v2 1/2] rerere: mention caveat about unmatched " Junio C Hamano
2018-09-01 9:00 ` Thomas Gummerer
2018-08-27 17:33 ` [PATCH v4 10/11] rerere: teach rerere to handle nested conflicts Junio C Hamano
2018-08-28 22:05 ` Thomas Gummerer
2018-08-27 19:36 ` Junio C Hamano
2018-08-05 17:20 ` [PATCH v4 11/11] rerere: recalculate conflict ID when unresolved conflict is committed Thomas Gummerer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180603114128.GD18193@hank.intra.tgummerer.com \
--to=t.gummerer@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).