darcs

Patch 2358 optimize conflict resolution in tentativelyMergePatches_

Title optimize conflict resolution in tentativelyMergePatches_
Superseder Nosy List bfrk
Related Issues
Status accepted Assigned To
Milestone

Created on 2023-08-24.16:48:03 by bfrk, last changed 2024-05-12.18:35:43 by bfrk.

Files
File name Status Uploaded Type Edit Remove
OpenPGP_0xD36E45316E58CC97.asc bfrk, 2024-05-12.18:35:42 application/pgp-keys
optimize-conflict-resolution-in-tentativelymergepatches_.dpatch bfrk, 2023-08-24.16:48:02 application/x-darcs-patch
patch-preview.txt bfrk, 2023-08-24.16:48:02 text/x-darcs-patch
See mailing list archives for discussion on individual patches.
Messages
msg23694 (view) Author: bfrk Date: 2023-08-24.16:48:02
1 patch for repository http://darcs.net/screened:

patch 5b159a9fcfaf16aad7cea8cf56d95ffa54a41e51
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Dec  3 15:46:23 CET 2022
  * optimize conflict resolution in tentativelyMergePatches_

  Examining patches for conflicts and then generating the markup is complex
  and scales poorly with the length of the sequence to be examined. So it
  makes sense to always choose the shorter of the two merged sequences to
  apply standardResolution on; the more so since in almost all cases occurring
  in practice the length of at least one of the two sequences is pretty short.
  However, this is only valid if the remote patches don't have unresolved
  conflicts in the first place. Detecting this condition requires another
  conflict resolution step, but one that is usually cheap because it can stop
  at the first clean tag.

  With this patch, pulling everything from a large repo (e.g. darcs screened)
  into an empty repository, while still not nearly as fast as a clone,
  completes in a reasonable time (and also doesn't run into darcs-2 commute
  bugs). This could be further improved by optimizing the process of updating
  the working tree which is a lot slower than updating pristine.
Attachments
msg23740 (view) Author: ganesh Date: 2024-02-18.16:51:28
Looks fine. I haven't thought in detail about whether conflict
resolution is symmetric like this but it seems reasonable.

> +          null $ conflictedPaths $ patchsetConflictResolutions $

Using "conflictedPaths" as the indicator of "are there any conflicts"
seems standard in other places in the code, but it does feel a bit
ugly. It doesn't seem intrinsic that a conflict has to be associated
with some path, though it's no doubt true right now, at least if
we ignore the already-broken setpref patches.
msg23797 (view) Author: bfrk Date: 2024-05-10.11:39:32
I agree, see issue2718.
msg23814 (view) Author: bfrk Date: 2024-05-12.18:35:42
> Looks fine. I haven't thought in detail about whether conflict

> resolution is symmetric like this but it seems reasonable.

Conflict resolution, in the abstract sense i.e. the set of conflicting 

alternative (prim) patch sequences that each apply at the end of the 

repo, should be order-independent. I think this follows from standard 

patch laws, since (apart from optimizations) each such sequence is 

calculated by commuting conflicting patches to the head.

For V3 we test this as a property. For V1/V2 I think it usually holds, 

though obviously I can't give any guarantees.
Attachments
History
Date User Action Args
2023-08-24 16:48:03bfrkcreate
2023-08-24 16:48:28bfrksetstatus: needs-screening -> needs-review
2024-02-18 16:51:28ganeshsetstatus: needs-review -> accepted-pending-tests
messages: + msg23740
2024-02-18 17:06:13ganeshsetstatus: accepted-pending-tests -> accepted
2024-05-10 11:39:32bfrksetmessages: + msg23797
2024-05-12 18:35:43bfrksetfiles: + OpenPGP_0xD36E45316E58CC97.asc
messages: + msg23814