@leroysheep / rag-system
Code Commits Pulls CI/CD 81,972
jch
bisect jch maint master next seen test todo
adoc 707 lines 29.7 KB
Raw
1 Rebases and cherry-picks involve a sequence of merges whose results are
2 recorded as new single-parent commits. The first parent side of those
3 merges represent the "upstream" side, and often include a far larger set of
4 changes than the second parent side. Traditionally, the renames on the
5 first-parent side of that sequence of merges were repeatedly re-detected
6 for every merge. This file explains why it is safe and effective during
7 rebases and cherry-picks to remember renames on the upstream side of
8 history as an optimization, assuming all merges are automatic and clean
9 (i.e. no conflicts and not interrupted for user input or editing).
10
11 Outline:
12
13 1. Assumptions
14
15 2. How rebasing and cherry-picking work
16
17 3. Why the renames on MERGE_SIDE1 in any given pick are *always* a
18 superset of the renames on MERGE_SIDE1 for the next pick.
19
20 4. Why any rename on MERGE_SIDE1 in any given pick is _almost_ always also
21 a rename on MERGE_SIDE1 for the next pick
22
23 5. A detailed description of the counter-examples to #4.
24
25 6. Why the special cases in #5 are still fully reasonable to use to pair
26 up files for three-way content merging in the merge machinery, and why
27 they do not affect the correctness of the merge.
28
29 7. Interaction with skipping of "irrelevant" renames
30
31 8. Additional items that need to be cached
32
33 9. How directory rename detection interacts with the above and why this
34 optimization is still safe even if merge.directoryRenames is set to
35 "true".
36
37
38 == 1. Assumptions ==
39
40 There are two assumptions that will hold throughout this document:
41
42 * The upstream side where commits are transplanted to is treated as the
43 first parent side when rebase/cherry-pick call the merge machinery
44
45 * All merges are fully automatic
46
47 and a third that will hold in sections 3-6 for simplicity, that I'll later
48 address in section 9:
49
50 * No directory renames occur
51
52
53 Let me explain more about each assumption and why I include it:
54
55
56 The first assumption is merely for the purposes of making this document
57 clearer; the optimization implementation does not actually depend upon it.
58 However, the assumption does hold in all cases because it reflects the way
59 that both rebase and cherry-pick were implemented; and the implementation
60 of cherry-pick and rebase are not readily changeable for backwards
61 compatibility reasons (see for example the discussion of the --ours and
62 --theirs flag in the documentation of `git checkout`, particularly the
63 comments about how they behave with rebase). The optimization avoids
64 checking first-parent-ness, though. It checks the conditions that make the
65 optimization valid instead, so it would still continue working if someone
66 changed the parent ordering that cherry-pick and rebase use. But making
67 this assumption does make this document much clearer and prevents me from
68 having to repeat every example twice.
69
70 If the second assumption is violated, then the optimization simply is
71 turned off and thus isn't relevant to consider. The second assumption can
72 also be stated as "there is no interruption for a user to resolve conflicts
73 or to just further edit or tweak files". While real rebases and
74 cherry-picks are often interrupted (either because it's an interactive
75 rebase where the user requested to stop and edit, or because there were
76 conflicts that the user needs to resolve), the cache of renames is not
77 stored on disk, and thus is thrown away as soon as the rebase or cherry
78 pick stops for the user to resolve the operation.
79
80 The third assumption makes sections 3-6 simpler, and allows people to
81 understand the basics of why this optimization is safe and effective, and
82 then I can go back and address the specifics in section 9. It is probably
83 also worth noting that if directory renames do occur, then the default of
84 merge.directoryRenames being set to "conflict" means that the operation
85 will stop for users to resolve the conflicts and the cache will be thrown
86 away, and thus that there won't be an optimization to apply. So, the only
87 reason we need to address directory renames specifically, is that some
88 users will have set merge.directoryRenames to "true" to allow the merges to
89 continue to proceed automatically. The optimization is still safe with
90 this config setting, but we have to discuss a few more cases to show why;
91 this discussion is deferred until section 9.
92
93
94 == 2. How rebasing and cherry-picking work ==
95
96 Consider the following setup (from the git-rebase manpage):
97
98 ------------
99 A---B---C topic
100 /
101 D---E---F---G main
102 ------------
103
104 After rebasing or cherry-picking topic onto main, this will appear as:
105
106 ------------
107 A'--B'--C' topic
108 /
109 D---E---F---G main
110 ------------
111
112 The way the commits A', B', and C' are created is through a series of
113 merges, where rebase or cherry-pick sequentially uses each of the three
114 A-B-C commits in a special merge operation. Let's label the three commits
115 in the merge operation as MERGE_BASE, MERGE_SIDE1, and MERGE_SIDE2. For
116 this picture, the three commits for each of the three merges would be:
117
118 ....
119 To create A':
120 MERGE_BASE: E
121 MERGE_SIDE1: G
122 MERGE_SIDE2: A
123
124 To create B':
125 MERGE_BASE: A
126 MERGE_SIDE1: A'
127 MERGE_SIDE2: B
128
129 To create C':
130 MERGE_BASE: B
131 MERGE_SIDE1: B'
132 MERGE_SIDE2: C
133 ....
134
135 Sometimes, folks are surprised that these three-way merges are done. It
136 can be useful in understanding these three-way merges to view them in a
137 slightly different light. For example, in creating C', you can view it as
138 either:
139
140 * Apply the changes between B & C to B'
141 * Apply the changes between B & B' to C
142
143 Conceptually the two statements above are the same as a three-way merge of
144 B, B', and C, at least the parts before you decide to record a commit.
145
146
147 == 3. Why the renames on MERGE_SIDE1 in any given pick are always a superset of the renames on MERGE_SIDE1 for the next pick. ==
148
149 The merge machinery uses the filenames it is fed from MERGE_BASE,
150 MERGE_SIDE1, and MERGE_SIDE2. It will only move content to a different
151 filename under one of three conditions:
152
153 * To make both pieces of a conflict available to a user during conflict
154 resolution (examples: directory/file conflict, add/add type conflict
155 such as symlink vs. regular file)
156
157 * When MERGE_SIDE1 renames the file.
158
159 * When MERGE_SIDE2 renames the file.
160
161 First, let's remember what commits are involved in the first and second
162 picks of the cherry-pick or rebase sequence:
163
164 ....
165 To create A':
166 MERGE_BASE: E
167 MERGE_SIDE1: G
168 MERGE_SIDE2: A
169
170 To create B':
171 MERGE_BASE: A
172 MERGE_SIDE1: A'
173 MERGE_SIDE2: B
174 ....
175
176 So, in particular, we need to show that the renames between E and G are a
177 superset of those between A and A'.
178
179 A' is created by the first merge. A' will only have renames for one of the
180 three reasons listed above. The first case, a conflict, results in a
181 situation where the cache is dropped and thus this optimization doesn't
182 take effect, so we need not consider that case. The third case, a rename
183 on MERGE_SIDE2 (i.e. from G to A), will show up in A' but it also shows up
184 in A -- therefore when diffing A and A' that path does not show up as a
185 rename. The only remaining way for renames to show up in A' is for the
186 rename to come from MERGE_SIDE1. Therefore, all renames between A and A'
187 are a subset of those between E and G. Equivalently, all renames between E
188 and G are a superset of those between A and A'.
189
190
191 == 4. Why any rename on MERGE_SIDE1 in any given pick is _almost_ always also a rename on MERGE_SIDE1 for the next pick. ==
192
193 Let's again look at the first two picks:
194
195 ....
196 To create A':
197 MERGE_BASE: E
198 MERGE_SIDE1: G
199 MERGE_SIDE2: A
200
201 To create B':
202 MERGE_BASE: A
203 MERGE_SIDE1: A'
204 MERGE_SIDE2: B
205 ....
206
207 Now let's look at any given rename from MERGE_SIDE1 of the first pick, i.e.
208 any given rename from E to G. Let's use the filenames 'oldfile' and
209 'newfile' for demonstration purposes. That first pick will function as
210 follows; when the rename is detected, the merge machinery will do a
211 three-way content merge of the following:
212
213 ....
214 E:oldfile
215 G:newfile
216 A:oldfile
217 ....
218
219 and produce a new result:
220
221 ....
222 A':newfile
223 ....
224
225 Note above that I've assumed that E->A did not rename oldfile. If that
226 side did rename, then we most likely have a rename/rename(1to2) conflict
227 that will cause the rebase or cherry-pick operation to halt and drop the
228 in-memory cache of renames and thus doesn't need to be considered further.
229 In the special case that E->A does rename the file but also renames it to
230 newfile, then there is no conflict from the renaming and the merge can
231 succeed. In this special case, the rename is not valid to cache because
232 the second merge will find A:newfile in the MERGE_BASE (see also the new
233 testcases in t6429 with "rename same file identically" in their
234 description). So a rename/rename(1to1) needs to be specially handled by
235 pruning renames from the cache and decrementing the dir_rename_counts in
236 the current and leading directories associated with those renames. Or,
237 since these are really rare, one could just take the easy way out and
238 disable the remembering renames optimization when a rename/rename(1to1)
239 happens.
240
241 The previous paragraph handled the cases for E->A renaming oldfile, let's
242 continue assuming that oldfile is not renamed in A.
243
244 As per the diagram for creating B', MERGE_SIDE1 involves the changes from A
245 to A'. So, we are curious whether A:oldfile and A':newfile will be viewed
246 as renames. Note that:
247
248 * There will be no A':oldfile (because there could not have been a
249 G:oldfile as we do not do break detection in the merge machinery and
250 G:newfile was detected as a rename, and by the construction of the
251 rename above that merged cleanly, the merge machinery will ensure there
252 is no 'oldfile' in the result).
253
254 * There will be no A:newfile (if there had been, we would have had a
255 rename/add conflict).
256
257 * Clearly A:oldfile and A':newfile are "related" (A':newfile came from a
258 clean three-way content merge involving A:oldfile).
259
260 We can also expound on the third point above, by noting that three-way
261 content merges can also be viewed as applying the differences between the
262 base and one side to the other side. Thus we can view A':newfile as
263 having been created by taking the changes between E:oldfile and G:newfile
264 (which were detected as being related, i.e. <50% changed) to A:oldfile.
265
266 Thus A:oldfile and A':newfile are just as related as E:oldfile and
267 G:newfile are -- they have exactly identical differences. Since the latter
268 were detected as renames, A:oldfile and A':newfile should also be
269 detectable as renames almost always.
270
271
272 == 5. A detailed description of the counter-examples to #4. ==
273
274 We already noted in section 4 that rename/rename(1to1) (i.e. both sides
275 renaming a file the same way) was one counter-example. The more
276 interesting bit, though, is why did we need to use the "almost" qualifier
277 when stating that A:oldfile and A':newfile are "almost" always detectable
278 as renames?
279
280 Let's repeat an earlier point that section 4 made:
281
282 ....
283 A':newfile was created by applying the changes between E:oldfile and
284 G:newfile to A:oldfile. The changes between E:oldfile and G:newfile were
285 <50% of the size of E:oldfile.
286 ....
287
288 If those changes that were <50% of the size of E:oldfile are also <50% of
289 the size of A:oldfile, then A:oldfile and A':newfile will be detectable as
290 renames. However, if there is a dramatic size reduction between E:oldfile
291 and A:oldfile (but the changes between E:oldfile, G:newfile, and A:oldfile
292 still somehow merge cleanly), then traditional rename detection would not
293 detect A:oldfile and A':newfile as renames.
294
295 Here's an example where that can happen:
296
297 * E:oldfile had 20 lines
298 * G:newfile added 10 new lines at the beginning of the file
299 * A:oldfile kept the first 3 lines of the file, and deleted all the rest
300
301 then
302
303 ....
304 => A':newfile would have 13 lines, 3 of which matches those in A:oldfile.
305 E:oldfile -> G:newfile would be detected as a rename, but A:oldfile and
306 A':newfile would not be.
307 ....
308
309
310 == 6. Why the special cases in #5 are still fully reasonable to use to pair up files for three-way content merging in the merge machinery, and why they do not affect the correctness of the merge. ==
311
312 In the rename/rename(1to1) case, A:newfile and A':newfile are not renames
313 since they use the *same* filename. However, files with the same filename
314 are obviously fine to pair up for three-way content merging (the merge
315 machinery has never employed break detection). The interesting
316 counter-example case is thus not the rename/rename(1to1) case, but the case
317 where A did not rename oldfile. That was the case that we spent most of
318 the time discussing in sections 4 and 5. The remainder of this section
319 will be devoted to that case as well.
320
321 So, even if A:oldfile and A':newfile aren't detectable as renames, why is
322 it still reasonable to pair them up for three-way content merging in the
323 merge machinery? There are multiple reasons:
324
325 * As noted in sections 4 and 5, the diff between A:oldfile and A':newfile
326 is *exactly* the same as the diff between E:oldfile and G:newfile. The
327 latter pair were detected as renames, so it seems unlikely to surprise
328 users for us to treat A:oldfile and A':newfile as renames.
329
330 * In fact, "oldfile" and "newfile" were at one point detected as renames
331 due to how they were constructed in the E..G chain. And we used that
332 information once already in this rebase/cherry-pick. I think users
333 would be unlikely to be surprised at us continuing to treat the files
334 as renames and would quickly understand why we had done so.
335
336 * Marking or declaring files as renames is *not* the end goal for merges.
337 Merges use renames to determine which files make sense to be paired up
338 for three-way content merges.
339
340 * A:oldfile and A':newfile were _already_ paired up in a three-way
341 content merge; that is how A':newfile was created. In fact, that
342 three-way content merge was clean. So using them again in a later
343 three-way content merge seems very reasonable.
344
345 However, the above is focusing on the common scenarios. Let's try to look
346 at all possible unusual scenarios and compare without the optimization to
347 with the optimization. Consider the following theoretical cases; we will
348 then dive into each to determine which of them are possible,
349 and if so, what they mean:
350
351 1. Without the optimization, the second merge results in a conflict.
352 With the optimization, the second merge also results in a conflict.
353 Questions: Are the conflicts confusingly different? Better in one case?
354
355 2. Without the optimization, the second merge results in NO conflict.
356 With the optimization, the second merge also results in NO conflict.
357 Questions: Are the merges the same?
358
359 3. Without the optimization, the second merge results in a conflict.
360 With the optimization, the second merge results in NO conflict.
361 Questions: Possible? Bug, bugfix, or something else?
362
363 4. Without the optimization, the second merge results in NO conflict.
364 With the optimization, the second merge results in a conflict.
365 Questions: Possible? Bug, bugfix, or something else?
366
367 I'll consider all four cases, but out of order.
368
369 The fourth case is impossible. For the code without the remembering
370 renames optimization to not get a conflict, B:oldfile would need to exactly
371 match A:oldfile -- if it doesn't, there would be a modify/delete conflict.
372 If A:oldfile matches B:oldfile exactly, then a three-way content merge
373 between A:oldfile, A':newfile, and B:oldfile would have no conflict and
374 just give us the version of newfile from A' as the result.
375
376 From the same logic as the above paragraph, the second case would indeed
377 result in identical merges. When A:oldfile exactly matches B:oldfile, an
378 undetected rename would say, "Oh, I see one side didn't modify 'oldfile'
379 and the other side deleted it. I'll delete it. And I see you have this
380 brand new file named 'newfile' in A', so I'll keep it." That gives the
381 same results as three-way content merging A:oldfile, A':newfile, and
382 B:oldfile -- a removal of oldfile with the version of newfile from A'
383 showing up in the result.
384
385 The third case is interesting. It means that A:oldfile and A':newfile were
386 not just similar enough, but that the changes between them did not conflict
387 with the changes between A:oldfile and B:oldfile. This would validate our
388 hunch that the files were similar enough to be used in a three-way content
389 merge, and thus seems entirely correct for us to have used them that way.
390 (Sidenote: One particular example here may be enlightening. Let's say that
391 B was an immediate revert of A. B clearly would have been a clean revert
392 of A, since A was B's immediate parent. One would assume that if you can
393 pick a commit, you should also be able to cherry-pick its immediate revert.
394 However, this is one of those funny corner cases; without this
395 optimization, we just successfully picked a commit cleanly, but we are
396 unable to cherry-pick its immediate revert due to the size differences
397 between E:oldfile and A:oldfile.)
398
399 That leaves only the first case to consider -- when we get conflicts both
400 with or without the optimization. Without the optimization, we'll have a
401 modify/delete conflict, where both A':newfile and B:oldfile are left in the
402 tree for the user to deal with and no hints about the potential similarity
403 between the two. With the optimization, we'll have a three-way content
404 merged A:oldfile, A':newfile, and B:oldfile with conflict markers
405 suggesting we thought the files were related but giving the user the chance
406 to resolve. As noted above, I don't think users will find us treating
407 'oldfile' and 'newfile' as related as a surprise since they were between E
408 and G. In any event, though, this case shouldn't be concerning since we
409 hit a conflict in both cases, told the user what we know, and asked them to
410 resolve it.
411
412 So, in summary, case 4 is impossible, case 2 yields the same behavior, and
413 cases 1 and 3 seem to provide as good or better behavior with the
414 optimization than without.
415
416
417 == 7. Interaction with skipping of "irrelevant" renames ==
418
419 Previous optimizations involved skipping rename detection for paths
420 considered to be "irrelevant". See for example the following commits:
421
422 * 32a56dfb99 ("merge-ort: precompute subset of sources for which we
423 need rename detection", 2021-03-11)
424 * 2fd9eda462 ("merge-ort: precompute whether directory rename
425 detection is needed", 2021-03-11)
426 * 9bd342137e ("diffcore-rename: determine which relevant_sources are
427 no longer relevant", 2021-03-13)
428
429 Relevance is always determined by what the _other_ side of history has
430 done, in terms of modifying a file that our side renamed, or adding a
431 file to a directory which our side renamed. This means that a path
432 that is "irrelevant" when picking the first commit of a series in a
433 rebase or cherry-pick, may suddenly become "relevant" when picking the
434 next commit.
435
436 The upshot of this is that we can only cache rename detection results
437 for relevant paths, and need to re-check relevance in subsequent
438 commits. If those subsequent commits have additional paths that are
439 relevant for rename detection, then we will need to redo rename
440 detection -- though we can limit it to the paths for which we have not
441 already detected renames.
442
443
444 == 8. Additional items that need to be cached ==
445
446 It turns out we have to cache more than just renames; we also cache:
447
448 ....
449 A) non-renames (i.e. unpaired deletes)
450 B) counts of renames within directories
451 C) sources that were marked as RELEVANT_LOCATION, but which were
452 downgraded to RELEVANT_NO_MORE
453 D) the toplevel trees involved in the merge
454 ....
455
456 These are all stored in struct rename_info, and respectively appear in
457
458 * cached_pairs (along side actual renames, just with a value of NULL)
459 * dir_rename_counts
460 * cached_irrelevant
461 * merge_trees
462
463 The reason for `(A)` comes from the irrelevant renames skipping
464 optimization discussed in section 7. The fact that irrelevant renames
465 are skipped means we only get a subset of the potential renames
466 detected and subsequent commits may need to run rename detection on
467 the upstream side on a subset of the remaining renames (to get the
468 renames that are relevant for that later commit). Since unpaired
469 deletes are involved in rename detection too, we don't want to
470 repeatedly check that those paths remain unpaired on the upstream side
471 with every commit we are transplanting.
472
473 The reason for `(B)` is that diffcore_rename_extended() is what
474 generates the counts of renames by directory which is needed in
475 directory rename detection, and if we don't run
476 diffcore_rename_extended() again then we need to have the output from
477 it, including dir_rename_counts, from the previous run.
478
479 The reason for `(C)` is that merge-ort's tree traversal will again think
480 those paths are relevant (marking them as RELEVANT_LOCATION), but the
481 fact that they were downgraded to RELEVANT_NO_MORE means that
482 dir_rename_counts already has the information we need for directory
483 rename detection. (A path which becomes RELEVANT_CONTENT in a
484 subsequent commit will be removed from cached_irrelevant.)
485
486 The reason for `(D)` is that is how we determine whether the remember
487 renames optimization can be used. In particular, remembering that our
488 sequence of merges looks like:
489
490 ....
491 Merge 1:
492 MERGE_BASE: E
493 MERGE_SIDE1: G
494 MERGE_SIDE2: A
495 => Creates A'
496
497 Merge 2:
498 MERGE_BASE: A
499 MERGE_SIDE1: A'
500 MERGE_SIDE2: B
501 => Creates B'
502 ....
503
504 It is the fact that the trees A and A' appear both in Merge 1 and in
505 Merge 2, with A as a parent of A' that allows this optimization. So
506 we store the trees to compare with what we are asked to merge next
507 time.
508
509
510 == 9. How directory rename detection interacts with the above and why this optimization is still safe even if merge.directoryRenames is set to "true". ==
511
512 As noted in the assumptions section:
513
514 ....
515 """
516 ...if directory renames do occur, then the default of
517 merge.directoryRenames being set to "conflict" means that the operation
518 will stop for users to resolve the conflicts and the cache will be
519 thrown away, and thus that there won't be an optimization to apply.
520 So, the only reason we need to address directory renames specifically,
521 is that some users will have set merge.directoryRenames to "true" to
522 allow the merges to continue to proceed automatically.
523 """
524 ....
525
526 Let's remember that we need to look at how any given pick affects the next
527 one. So let's again use the first two picks from the diagram in section
528 one:
529
530 ....
531 First pick does this three-way merge:
532 MERGE_BASE: E
533 MERGE_SIDE1: G
534 MERGE_SIDE2: A
535 => creates A'
536
537 Second pick does this three-way merge:
538 MERGE_BASE: A
539 MERGE_SIDE1: A'
540 MERGE_SIDE2: B
541 => creates B'
542 ....
543
544 Now, directory rename detection exists so that if one side of history
545 renames a directory, and the other side adds a new file to the old
546 directory, then the merge (with merge.directoryRenames=true) can move the
547 file into the new directory. There are two qualitatively different ways to
548 add a new file to an old directory: create a new file, or rename a file
549 into that directory. Also, directory renames can be done on either side of
550 history, so there are four cases to consider:
551
552 * MERGE_SIDE1 renames old dir, MERGE_SIDE2 adds new file to old dir
553 * MERGE_SIDE1 renames old dir, MERGE_SIDE2 renames file into old dir
554 * MERGE_SIDE1 adds new file to old dir, MERGE_SIDE2 renames old dir
555 * MERGE_SIDE1 renames file into old dir, MERGE_SIDE2 renames old dir
556
557 One last note before we consider these four cases: There are some
558 important properties about how we implement this optimization with
559 respect to directory rename detection that we need to bear in mind
560 while considering all of these cases:
561
562 * rename caching occurs *after* applying directory renames
563
564 * a rename created by directory rename detection is recorded for the side
565 of history that did the directory rename.
566
567 * dir_rename_counts, the nested map of
568 {oldname => {newname => count}},
569 is cached between runs as well. This basically means that directory
570 rename detection is also cached, though only on the side of history
571 that we cache renames for (MERGE_SIDE1 as far as this document is
572 concerned; see the assumptions section). Two interesting sub-notes
573 about these counts:
574
575 ** If we need to perform rename-detection again on the given side (e.g.
576 some paths are relevant for rename detection that weren't before),
577 then we clear dir_rename_counts and recompute it, making use of
578 cached_pairs. The reason it is important to do this is optimizations
579 around RELEVANT_LOCATION exist to prevent us from computing
580 unnecessary renames for directory rename detection and from computing
581 dir_rename_counts for irrelevant directories; but those same renames
582 or directories may become necessary for subsequent merges. The
583 easiest way to "fix up" dir_rename_counts in such cases is to just
584 recompute it.
585
586 ** If we prune rename/rename(1to1) entries from the cache, then we also
587 need to update dir_rename_counts to decrement the counts for the
588 involved directory and any relevant parent directories (to undo what
589 update_dir_rename_counts() in diffcore-rename.c incremented when the
590 rename was initially found). If we instead just disable the
591 remembering renames optimization when the exceedingly rare
592 rename/rename(1to1) cases occur, then dir_rename_counts will get
593 re-computed the next time rename detection occurs, as noted above.
594
595 * the side with multiple commits to pick, is the side of history that we
596 do NOT cache renames for. Thus, there are no additional commits to
597 change the number of renames in a directory, except for those done by
598 directory rename detection (which always pad the majority).
599
600 * the "renames" we cache are modified slightly by any directory rename,
601 as noted below.
602
603 Now, with those notes out of the way, let's go through the four cases
604 in order:
605
606 Case 1: MERGE_SIDE1 renames old dir, MERGE_SIDE2 adds new file to old dir
607
608 ....
609 This case looks like this:
610
611 MERGE_BASE: E, Has olddir/
612 MERGE_SIDE1: G, Renames olddir/ -> newdir/
613 MERGE_SIDE2: A, Adds olddir/newfile
614 => creates A', With newdir/newfile
615
616 MERGE_BASE: A, Has olddir/newfile
617 MERGE_SIDE1: A', Has newdir/newfile
618 MERGE_SIDE2: B, Modifies olddir/newfile
619 => expected B', with threeway-merged newdir/newfile from above
620
621 In this case, with the optimization, note that after the first commit:
622 * MERGE_SIDE1 remembers olddir/ -> newdir/
623 * MERGE_SIDE1 has cached olddir/newfile -> newdir/newfile
624 Given the cached rename noted above, the second merge can proceed as
625 expected without needing to perform rename detection from A -> A'.
626 ....
627
628 Case 2: MERGE_SIDE1 renames old dir, MERGE_SIDE2 renames file into old dir
629
630 ....
631 This case looks like this:
632
633 MERGE_BASE: E oldfile, olddir/
634 MERGE_SIDE1: G oldfile, olddir/ -> newdir/
635 MERGE_SIDE2: A oldfile -> olddir/newfile
636 => creates A', With newdir/newfile representing original oldfile
637
638 MERGE_BASE: A olddir/newfile
639 MERGE_SIDE1: A' newdir/newfile
640 MERGE_SIDE2: B modify olddir/newfile
641 => expected B', with threeway-merged newdir/newfile from above
642
643 In this case, with the optimization, note that after the first commit:
644 * MERGE_SIDE1 remembers olddir/ -> newdir/
645 * MERGE_SIDE1 has cached olddir/newfile -> newdir/newfile
646 (NOT oldfile -> newdir/newfile; compare to case with
647 (p->status == 'R' && new_path) in possibly_cache_new_pair())
648
649 Given the cached rename noted above, the second merge can proceed as
650 expected without needing to perform rename detection from A -> A'.
651 ....
652
653 Case 3: MERGE_SIDE1 adds new file to old dir, MERGE_SIDE2 renames old dir
654
655 ....
656 This case looks like this:
657
658 MERGE_BASE: E, Has olddir/
659 MERGE_SIDE1: G, Adds olddir/newfile
660 MERGE_SIDE2: A, Renames olddir/ -> newdir/
661 => creates A', With newdir/newfile
662
663 MERGE_BASE: A, Has newdir/, but no notion of newdir/newfile
664 MERGE_SIDE1: A', Has newdir/newfile
665 MERGE_SIDE2: B, Has newdir/, but no notion of newdir/newfile
666 => expected B', with newdir/newfile from A'
667
668 In this case, with the optimization, note that after the first commit there
669 were no renames on MERGE_SIDE1, and any renames on MERGE_SIDE2 are tossed.
670 But the second merge didn't need any renames so this is fine.
671 ....
672
673 Case 4: MERGE_SIDE1 renames file into old dir, MERGE_SIDE2 renames old dir
674
675 ....
676 This case looks like this:
677
678 MERGE_BASE: E, Has olddir/
679 MERGE_SIDE1: G, Renames oldfile -> olddir/newfile
680 MERGE_SIDE2: A, Renames olddir/ -> newdir/
681 => creates A', With newdir/newfile representing original oldfile
682
683 MERGE_BASE: A, Has oldfile
684 MERGE_SIDE1: A', Has newdir/newfile
685 MERGE_SIDE2: B, Modifies oldfile
686 => expected B', with threeway-merged newdir/newfile from above
687
688 In this case, with the optimization, note that after the first commit:
689 * MERGE_SIDE1 remembers oldfile -> newdir/newfile
690 (NOT oldfile -> olddir/newfile; compare to case of second
691 block under p->status == 'R' in possibly_cache_new_pair())
692 * MERGE_SIDE2 renames are tossed because only MERGE_SIDE1 is remembered
693
694 Given the cached rename noted above, the second merge can proceed as
695 expected without needing to perform rename detection from A -> A'.
696 ....
697
698 Finally, I'll just note here that interactions with the
699 skip-irrelevant-renames optimization means we sometimes don't detect
700 renames for any files within a directory that was renamed, in which
701 case we will not have been able to detect any rename for the directory
702 itself. In such a case, we do not know whether the directory was
703 renamed; we want to be careful to avoid caching some kind of "this
704 directory was not renamed" statement. If we did, then a subsequent
705 commit being rebased could add a file to the old directory, and the
706 user would expect it to end up in the correct directory -- something
707 our erroneous "this directory was not renamed" cache would preclude.