Hi, Sorry for the lengthy email, but I'm still working on my patch series auditing merge-recursive corner cases, and I've run into criss-cross merges that I don't know how to solve. In some cases, even the 'right' answer (in terms of what unmerged entries the index should contain when there are conflicts) isn't entirely clear to me, much less how to implement it. I'm hoping someone else has some bright ideas. The basic setup is the following: # B D # o---o # / \ / \ # A o X ? F # \ / \ / # o---o # C E In other words, there Let's start with a simple though very contrived case that will illustrate issues later, namely a repository with exactly one file named 'file', with the following contents at different points in history: Commit A: file has contents 'A\n' Commit B: file has contents 'B\n' Commit C: file has contents 'C\n' Commit D: file has contents 'D\n' Commit E: file has the following 5 lines in it: <<<<<<< Temporary merge branch 1 C ======= B >>>>>>> Temporary merge branch 2 Now, if we try to merge D & E, clearly there should be a conflict. But git merges cleanly, giving file the contents 'D\n'. The reason for this is that git notices there are two merge bases, B & C, tries to merge them in-core, notices the conflict, stores the 3-way merged contents as the version of 'file' in the new virtual ancestor, and then does a three-way merge between that virtual ancestor and D & E. Since the contents of 'file' match between the virtual ancestor and E, the contents of file from D are selected as the merge resolution. It's wrong, but the only way to fix it is to somehow have an entry in the virtual ancestor tree where the conflict region(s) of file are guaranteed to not match the corresponding content locations of file for either D or E. (Perhaps by adding random content on the line after the ='s?) Given the extremely contrived nature of this example, perhaps we don't care. But the basic problem that we need some kind of entry in the virtual ancestor that makes sense for a conflict case can come up in other less-contrived scenarios. For example, with directory/file conflicts... Let's look at a slightly more complicated example, a repository with up to three files: 'junk', 'a' and 'a/file': Commit A: Only 'junk' exists Commit B: Adds file 'a' Commit C: Adds file 'a/file' Commit D: Merges B & C, keeping 'a' and deleting 'a/file' Commit E: Merges B & C, deleting 'a' but keeping 'a/file' Now, merging D & E should result in a (directory/file) conflict, with both 'a' and 'a/file' left in the index (at stages 2 and 3 -- what, if anything, exists at stage 1 is unclear to me) and both 'a/file' and 'a~<branch>' existing in the working copy. But how/if that happens, depends on the virtual ancestor created when merging B & C in-core. Possibilities: Possibility 1: Virtual ancestor somehow contains both 'a' and 'a/file' (currently impossible in git, since this virtual ancestor is written as a tree and there's code to prevent writing trees with D/F conflicts). This would mean that 'a' is unchanged between the virtual ancestor and D and thus should be deleted as in E. Also, 'a/file' is unchanged between the virtual ancestor and E and thus should be deleted as in D. So we get a clean merge without either 'a' or 'a/file' present. Bad. Possibility 2: Virtual ancestor contains 'a' but not 'a/file'. This means the virtual ancestor matches commit D exactly, so git can cleanly merge by just selecting the contents of E. Bad. Possibility 3: Virtual ancestor contains 'a/file' but not 'a'. Like possibility 2, in reverse: this time the merge is clean having the contents of D. Bad. Possibility 4: Virtual ancestor contains neither 'a' nor 'a/file'. This case will correctly detect an (add/add) conflict of the directory/file variety. Stage 1 will be empty, but stages 2 and 3 will have the appropriate contents. So possibility 4 sounds great, right? Let's say we use that algorithm, but now we have a different situation: Commits A, B, C, & D: all as above Commit E2: Merges B & C, keeping a slightly modified version of 'a' and deleting 'a/file'. Merging D & E2 should be clean, with 'a/file' being removed (since both D and E2 removed it) and the slightly modified version of 'a' from E2 appearing in the result (since 'a' is unmodified in D). However, having the virtual ancestor contain neither 'a' nor 'a/file' will cause an add/add conflict when merging D & E2. Bad. The only way out of this that I see (and I'm hoping I'm just missing something), is a modification of possibility 1: make the virtual ancestor contain both 'a' and 'a/file', but with both files modified somehow to ensure they don't match the contents of D, E, or E2 (maybe by appending some random data? something extremely unlikely to match the contents of the file in any of D, E, or E2 such as a timestamp?). That would result in merging D & E giving the appropriate conflict (detected as a modify/delete), and merging D & E2 to go cleanly so long as the modification of 'a' in E2 didn't appear near the random modification of 'a' in the virtual ancestor. Ugh. Seems like a mess. Anyone have any bright ideas? Elijah -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html