Stefan Sperling wrote on Mon, 16 Nov 2009 at 14:39 +0100: > Julian asked for a formal description of how 'svn patch' applies > hunks. Below are my current plans. The current code does something > quite different and will be changed to implement what is described > below before 1.7 release.
Okay, good to know. > ... (lots of text, read it, sounds sensible, but haven't tried to think "how else could it be done?".) > The goals of the hunk-application algorithm are: > 1) Memory usage is bound by the longest line occurring in the patch file "bounded" > Let C represent the current index into the lists of candidate offsets. > Set C = 1 (indexing the first candidate offset). > Iterate over the list of hunks. > If the hunk is already marked applied or rejected, ignore it. > If the hunk's Cth candidate offset is not contained in any range described > by the list of occupied lines, store its current candidate offset and the > length of its original text in the list of occupied line ranges and mark > the hunk as applied. > Else, if the hunk is not marked applied, and its current candidate offset > is within the range of occupied lines, defer handling of this hunk to the > next iteration. > If the hunk has no Cth candidate offset, mark the hunk as rejected. > Increment C and iterate. > i.e., iterate all 1st candidates, then all 2nd candidates, etc. Why not iterate by hunks first? (i.e., first all candidates of 1st hunk, then all candidates of 2nd hunk, etc.) > After this step, all hunks are marked either applied or rejected. > If any hunks were rejected and rejection is not allowed, raise an error. > > Repeat the above process for the next patch target. > If the first target applies cleanly and the second contains rejected hunk, do we prompt the user before modifying the first target? (if not, we might partially-apply a patch, only to some of the files it touches) > Once all patch targets are processed as above, read each target file again > from the top, copying lines not contained in the list of lines occupied by > hunks verbatim. Replace any lines occupied by a hunk with lines of the hunk's > modified text. > (Note that the number of lines in the modified text of a hunk may differ > from the number of lines in the original text of a hunk, so the patched > file can have a different number of lines than the original file. All offsets > are relative to the original file, however.) > > Write any rejected hunks for this target to a reject file. > In what format? > The patch is now applied. Daniel (btw... would be nice to use this code with non-svn patches. Especially since it has interactive conflict resolution now...)
