{"thread":{"id":"1743","subject":"[PATCH 0/2] A new merge algorithm, take 3","startedAt":"2005-09-07T16:47:34Z","lastAt":"2005-09-20T05:50:22Z","messageCount":40,"participants":["Fredrik Kuivinen","Daniel Barkalow","Junio C Hamano","Chuck Lever","Linus Torvalds","A Large Angry SCM"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"8164","messageId":"20050907164734.GA20198@c165.ib.student.liu.se","threadId":"1743","inReplyTo":null,"subject":"[PATCH 0/2] A new merge algorithm, take 3","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-07T16:47:34Z","receivedAt":"2005-09-07T16:47:34Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"Hi,\n\nHere is the new version of the merge algorithm patch.\n\nThe major changes compared to the previous patch are:\n\n* No more messing around with merge-cache. git-ls-files used to get\n the unmerged entries instead.\n* The python code is now contained in two files, git-merge-script and\n gitMergeCommon.py.\n* The user interface is identical to the interface provided by\n git-resolve-script\n* In the non-clean case the unmerged cache entries will not be\n removed from the cache.\n\nI have also attached a test script which can redo every merge in a\nrepository with both git-resolve-script and git-merge-script. It will\nreport any non-clean merges and non-identical results for clean\nmerges. Do _not_ use this script in repositories you care about. It\ncalls 'git reset --hard' repeatedly and will probably not leave the\nrepository in its original state when it's done.\n\nOf the 500 merge commits that currently exists in the kernel\nrepository 19 produces non-clean merges with git-merge-script. The\nfour merge cases listed in\n<20050827014009.GB18880@c165.ib.student.liu.se> are cleanly merged by\ngit-merge-script. Every merge commit which is cleanly merged by\ngit-resolve-script is also cleanly merged by git-merge-script,\nfurthermore the results are identical. There are currently two merges\nin the kernel repository which are not cleanly merged by\ngit-resolve-script but are cleanly merged by git-merge-script.\n\nI guess the need for this has decreased with Daniel's new read-tree\ncode. Is there any chance of getting this code merged into mainline\ngit?\n\n- Fredrik\n\n\n#!/usr/bin/env python\n\nimport sys, math, random, os, re, signal, tempfile, time\nfrom heapq import heappush, heappop\nfrom sets import Set\nfrom gitMergeCommon import *\n\ndef mergeMerge(a, b):\n print 'Running merge-script HEAD', b.sha, '...'\n [out, code] = runProgram(['git-merge-script', 'HEAD', b.sha, 'merge message'],\n returnCode=True, pipeOutput=False)\n if code == 0:\n return True\n else:\n return False\n \ndef gitResolveMerge(a, b):\n print 'Running git resolve HEAD', b.sha, '...'\n [out, code] = runProgram(['git', 'resolve', 'HEAD', b.sha, 'merge message'],\n returnCode=True, pipeOutput=False)\n\n if code == 0:\n return True\n else:\n return False\n\ndef doWork(graph, commits):\n print 'commits:', repr(commits)\n result = []\n totalMergeTime = 0\n totalResolveTime = 0\n numCommits = 0\n try:\n for commit in graph.commits:\n if len(commits) > 0 and not (commit.sha in commits):\n continue\n\n if len(commit.parents) > 1:\n res = commit.sha + ' : '\n if len(commit.parents) == 2:\n numCommits += 1\n print '---------------------------------------'\n print 'Testing commit', commit.sha, '(tree)', commit.tree()\n a = commit.parents[0]\n b = commit.parents[1]\n\n runProgram(['git-reset-script', '--hard', a.sha])\n print 'Running git resolve...'\n stdout.flush()\n startTime = time.time()\n resResolve = gitResolveMerge(a, b)\n timeResolve = time.time() - startTime\n totalResolveTime += timeResolve\n \n if resResolve:\n resolveHead = Commit(runProgram(['git-rev-parse', '--verify', 'HEAD']).rstrip(), [a, b])\n\n runProgram(['git-reset-script', '--hard', a.sha])\n print 'Running merge...'\n stdout.flush()\n startTime = time.time()\n resMerge = mergeMerge(a, b)\n timeMerge = time.time() - startTime\n totalMergeTime += timeMerge\n \n if resMerge:\n mergeHead = Commit(runProgram(['git-rev-parse', '--verify', 'HEAD']).rstrip(), [a, b])\n\n res += 'time r: ' + str(int(timeResolve)) + ' m: ' + str(int(timeMerge)) + '\\t'\n if resResolve and resMerge:\n if resolveHead.tree() == mergeHead.tree():\n res += 'Identical result'\n else:\n res += 'Non-identical results! resolve: ' + resolveHead.sha + \\\n ' merge: ' + mergeHead.sha\n else:\n if resResolve:\n res += 'resolve succeeded (' + resolveHead.sha + '), '\n else:\n res += 'resolve failed, '\n\n if resMerge:\n res += 'merge succeeded (' + mergeHead.sha + ')'\n else:\n res += 'merge failed'\n else:\n res += 'Ignoring octupus merge'\n\n print res\n result.append(res)\n stdout.flush()\n finally:\n print '\\n\\n\\nResults:'\n for r in result:\n print r\n print 'Avg resolve time:', float(totalResolveTime) / numCommits\n print 'Avg merge time:', float(totalMergeTime) / numCommits\n\ndef writeHead(head, sha):\n if sha[-1] != '\\n':\n sha += '\\n'\n\n try:\n f = open(os.environ['GIT_DIR'] + '/' + head, 'w')\n f.write(sha)\n f.close()\n except IOError, e:\n print 'Failed to write to', os.environ['GIT_DIR'] + '/' + head + ':', e.strerror\n sys.exit(1)\n return True\n\nstdout = sys.stdout\nsetupEnvironment()\nrepoValid()\n\nhead = runProgram(['git-rev-parse', '--verify', 'HEAD^0']).rstrip()\nprint 'Building graph...'\nstdout.flush()\ngraph = buildGraph([head])\nprint 'Graph building done.'\nstdout.flush()\nprint 'Processing', len(graph.commits), 'commits (' + \\\n str(len([x for x in graph.commits if len(x.parents) > 1])) + ' merge commits)...'\n\noriginalHead = open('.git/HEAD', 'r').read()\nprint 'Original head:', originalHead\nstdout.flush()\n\nwriteHead('original-head', originalHead)\n\ntry:\n doWork(graph, sys.argv[1:])\nfinally:\n writeHead('HEAD', originalHead)\n"},{"id":"8165","messageId":"20050907165012.GA20392@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"20050907164734.GA20198@c165.ib.student.liu.se","subject":"[PATCH 1/2] Add '-i' flag to read-tree to make it ignore whats in the working directory.","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-07T16:50:12Z","receivedAt":"2005-09-07T16:50:12Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"This will be used by the merge code.\n\nSigned-off-by: Fredrik Kuivinen \n\n\n---\n\n read-tree.c | 13 +++++++++++--\n 1 files changed, 11 insertions(+), 2 deletions(-)\n\n12d226103dc278c5d5aaf6b2dc776af3170ed233\ndiff --git a/read-tree.c b/read-tree.c\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -7,6 +7,7 @@\n \n static int stage = 0;\n static int update = 0;\n+static int ignore_working_dir = 0;\n \n static int unpack_tree(unsigned char *sha1)\n {\n@@ -80,7 +81,10 @@ static void verify_uptodate(struct cache\n {\n \tstruct stat st;\n \n-\tif (!lstat(ce->name, &st)) {\n+ if (ignore_working_dir)\n+ return;\n+\n+ if (!lstat(ce->name, &st)) {\n \t\tunsigned changed = ce_match_stat(ce, &st);\n \t\tif (!changed)\n \t\t\treturn;\n@@ -510,7 +514,7 @@ static int read_cache_unmerged(void)\n \treturn deleted;\n }\n \n-static const char read_tree_usage[] = \"git-read-tree ( | -m [-u] [ []])\";\n+static const char read_tree_usage[] = \"git-read-tree ( | -m [-u] [-i] [ []])\";\n \n static struct cache_file cache_file;\n \n@@ -535,6 +539,11 @@ int main(int argc, char **argv)\n \t\t\tcontinue;\n \t\t}\n \n+ if (!strcmp(arg, \"-i\")) {\n+ ignore_working_dir = 1;\n+ continue;\n+ }\n+\n \t\t/* This differs from \"-m\" in that we'll silently ignore unmerged entries */\n \t\tif (!strcmp(arg, \"--reset\")) {\n \t\t\tif (stage || merge || emu23)\n"},{"id":"8166","messageId":"20050907165141.GB20392@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"20050907164734.GA20198@c165.ib.student.liu.se","subject":"[PATCH 2/2] A new merge algorithm","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-07T16:51:41Z","receivedAt":"2005-09-07T16:51:41Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"The new algorithm handles multiple common ancestors in a better way.\n\nSigned-off-by: Fredrik Kuivinen \n\n\n---\n\n Makefile | 3 \n git-merge-script | 491 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n gitMergeCommon.py | 286 +++++++++++++++++++++++++++++++\n 3 files changed, 779 insertions(+), 1 deletions(-)\n create mode 100644 git-merge-script\n create mode 100644 gitMergeCommon.py\n\n4c86af6fac9d0f527c277c88d7ae3d200dd24f61\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -66,7 +66,8 @@ SCRIPTS=git git-merge-one-file-script gi\n \tgit-format-patch-script git-sh-setup-script git-push-script \\\n \tgit-branch-script git-parse-remote-script git-verify-tag-script \\\n \tgit-ls-remote-script git-rename-script \\\n-\tgit-request-pull-script git-bisect-script\n+\tgit-request-pull-script git-bisect-script gitMergeCommon.py \\\n+\tgit-merge-script\n \n SCRIPTS += git-count-objects-script\n SCRIPTS += git-revert-script\ndiff --git a/git-merge-script b/git-merge-script\nnew file mode 100755\n--- /dev/null\n+++ b/git-merge-script\n@@ -0,0 +1,491 @@\n+#!/usr/bin/env python\n+\n+import sys, math, random, os, re, signal, tempfile, stat, errno\n+from heapq import heappush, heappop\n+from sets import Set\n+from gitMergeCommon import *\n+\n+alwaysWriteTree = False\n+\n+# The actual merge code\n+# ---------------------\n+\n+def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):\n+ '''Merge the commits h1 and h2, return the resulting virtual\n+ commit object and a flag indicating the cleaness of the merge.'''\n+ assert(isinstance(h1, Commit) and isinstance(h2, Commit))\n+ assert(isinstance(graph, Graph))\n+\n+ def infoMsg(*args):\n+ sys.stdout.write(' '*callDepth)\n+ printList(args)\n+ infoMsg('Merging:')\n+ infoMsg(h1)\n+ infoMsg(h2)\n+ sys.stdout.flush()\n+\n+ ca = getCommonAncestors(graph, h1, h2)\n+ infoMsg('found', len(ca), 'common ancestor(s):')\n+ for x in ca:\n+ infoMsg(x)\n+ sys.stdout.flush()\n+\n+ Ms = ca[0]\n+ for h in ca[1:]:\n+ [Ms, ignore] = merge(Ms, h,\n+ 'Temporary shared merge branch 1',\n+ 'Temporary shared merge branch 2',\n+ graph, callDepth+1)\n+ assert(isinstance(Ms, Commit))\n+\n+ if callDepth == 0:\n+ if len(ca) > 1:\n+ runProgram(['git-read-tree', h1.tree()])\n+ runProgram(['git-update-cache', '-q', '--refresh'])\n+ # Use the original index if we only have one common ancestor\n+ \n+ updateWd = True\n+ if alwaysWriteTree:\n+ cleanCache = True\n+ else:\n+ cleanCache = False\n+ else:\n+ runProgram(['git-read-tree', h1.tree()])\n+ updateWd = False\n+ cleanCache = True\n+\n+ [shaRes, clean] = mergeTrees(h1.tree(), h2.tree(), Ms.tree(),\n+ branch1Name, branch2Name,\n+ cleanCache, updateWd)\n+\n+ if clean or alwaysWriteTree:\n+ res = Commit(None, [h1, h2], tree=shaRes)\n+ graph.addNode(res)\n+ else:\n+ res = None\n+\n+ return [res, clean]\n+\n+getFilesRE = re.compile('([0-9]+) ([a-z0-9]+) ([0-9a-f]{40})\\t(.*)')\n+def getFilesAndDirs(tree):\n+ files = Set()\n+ dirs = Set()\n+ out = runProgram(['git-ls-tree', '-r', '-z', tree])\n+ for l in out.split('\\0'):\n+ m = getFilesRE.match(l)\n+ if m:\n+ if m.group(2) == 'tree':\n+ dirs.add(m.group(4))\n+ elif m.group(2) == 'blob':\n+ files.add(m.group(4))\n+\n+ return [files, dirs]\n+\n+class CacheEntry:\n+ def __init__(self, path):\n+ class Stage:\n+ def __init__(self):\n+ self.sha1 = None\n+ self.mode = None\n+ \n+ self.stages = [Stage(), Stage(), Stage()]\n+ self.path = path\n+\n+unmergedRE = re.compile('^([0-9]+) ([0-9a-f]{40}) ([1-3])\\t(.*)$')\n+def unmergedCacheEntries():\n+ '''Create a dictionary mapping file names to CacheEntry\n+ objects. The dictionary contains one entry for every path with a\n+ non-zero stage entry.'''\n+\n+ lines = runProgram(['git-ls-files', '-z', '--unmerged']).split('\\0')\n+ lines.pop()\n+\n+ res = {}\n+ for l in lines:\n+ m = unmergedRE.match(l)\n+ if m:\n+ mode = int(m.group(1), 8)\n+ sha1 = m.group(2)\n+ stage = int(m.group(3)) - 1\n+ path = m.group(4)\n+\n+ if res.has_key(path):\n+ e = res[path]\n+ else:\n+ e = CacheEntry(path)\n+ res[path] = e\n+ \n+ e.stages[stage].mode = mode\n+ e.stages[stage].sha1 = sha1\n+ else:\n+ print 'Error: Merge program failed: Unexpected output from', \\\n+ 'git-ls-files:', l\n+ sys.exit(1)\n+ return res\n+\n+def mergeTrees(head, merge, common, branch1Name, branch2Name,\n+ cleanCache, updateWd):\n+ '''Merge the trees 'head' and 'merge' with the common ancestor\n+ 'common'. The name of the head branch is 'branch1Name' and the name of\n+ the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)\n+ where tree is the resulting tree and cleanMerge is True iff the\n+ merge was clean.'''\n+ \n+ assert(isSha(head) and isSha(merge) and isSha(common))\n+\n+ if common == merge:\n+ print 'Already uptodate!'\n+ return [head, True]\n+\n+ if updateWd:\n+ updateArg = '-u'\n+ else:\n+ updateArg = '-i'\n+ runProgram(['git-read-tree', updateArg, '-m', common, head, merge])\n+ cleanMerge = True\n+\n+ [tree, code] = runProgram('git-write-tree', returnCode=True)\n+ tree = tree.rstrip()\n+ if code != 0:\n+ [files, dirs] = getFilesAndDirs(head)\n+ [filesM, dirsM] = getFilesAndDirs(merge)\n+ files.union_update(filesM)\n+ dirs.union_update(dirsM)\n+ \n+ cleanMerge = True\n+ entries = unmergedCacheEntries()\n+ for name in entries:\n+ if not processEntry(entries[name], branch1Name, branch2Name,\n+ files, dirs, cleanCache, updateWd):\n+ cleanMerge = False\n+ \n+ if cleanMerge or cleanCache:\n+ tree = runProgram('git-write-tree').rstrip()\n+ else:\n+ tree = None\n+ else:\n+ cleanMerge = True\n+\n+ return [tree, cleanMerge]\n+\n+def processEntry(entry, branch1Name, branch2Name, files, dirs,\n+ cleanCache, updateWd):\n+ '''Merge one cache entry. 'files' is a Set with the files in both of\n+ the heads that we are going to merge. 'dirs' contains the\n+ corresponding data for directories. If 'cleanCache' is True no\n+ non-zero stages will be left in the cache for the path\n+ corresponding to the entry 'entry'.'''\n+\n+# cleanCache == True => Don't leave any non-stage 0 entries in the cache.\n+# False => Leave unmerged entries\n+\n+# updateWd == True => Update the working directory to correspond to the cache\n+# False => Leave the working directory unchanged\n+\n+# clean == True => non-conflict case\n+# False => conflict case\n+\n+# If cleanCache == False then the cache shouldn't be updated if clean == False\n+\n+ def updateFile(clean, sha, mode, path):\n+ if cleanCache or (not cleanCache and clean):\n+ runProgram(['git-update-cache', '--add', '--cacheinfo',\n+ '0%o' % mode, sha, path])\n+\n+ if updateWd:\n+ prog = ['git-cat-file', 'blob', sha]\n+ if stat.S_ISREG(mode):\n+ try:\n+ os.unlink(path)\n+ except OSError:\n+ pass\n+ if mode & 0100:\n+ mode = 0777\n+ else:\n+ mode = 0666\n+ fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)\n+ proc = subprocess.Popen(prog, stdout=fd)\n+ proc.wait()\n+ os.close(fd)\n+ elif stat.S_ISLNK(mode):\n+ linkTarget = runProgram(prog)\n+ os.symlink(linkTarget, path)\n+ else:\n+ assert(False)\n+ runProgram(['git-update-cache', '--', path])\n+\n+ def removeFile(clean, path):\n+ if cleanCache or (not cleanCache and clean):\n+ runProgram(['git-update-cache', '--force-remove', '--', path])\n+\n+ if updateWd:\n+ try:\n+ os.unlink(path)\n+ except OSError, e:\n+ if e.errno != errno.ENOENT and e.errno != errno.EISDIR:\n+ raise\n+\n+ def uniquePath(path, branch):\n+ newPath = path + '_' + branch\n+ suffix = 0\n+ while newPath in files or newPath in dirs:\n+ suffix += 1\n+ newPath = path + '_' + branch + '_' + str(suffix)\n+ files.add(newPath)\n+ return newPath\n+\n+ debug('processing', entry.path, 'clean cache:', cleanCache,\n+ 'wd:', updateWd)\n+\n+ cleanMerge = True\n+\n+ path = entry.path\n+ oSha = entry.stages[0].sha1\n+ oMode = entry.stages[0].mode\n+ aSha = entry.stages[1].sha1\n+ aMode = entry.stages[1].mode\n+ bSha = entry.stages[2].sha1\n+ bMode = entry.stages[2].mode\n+\n+ assert(oSha == None or isSha(oSha))\n+ assert(aSha == None or isSha(aSha))\n+ assert(bSha == None or isSha(bSha))\n+\n+ assert(oMode == None or type(oMode) is int)\n+ assert(aMode == None or type(aMode) is int)\n+ assert(bMode == None or type(bMode) is int)\n+\n+ if (oSha and (not aSha or not bSha)):\n+ #\n+ # Case A: Deleted in one\n+ #\n+ if (not aSha and not bSha) or \\\n+ (aSha == oSha and not bSha) or \\\n+ (not aSha and bSha == oSha):\n+ # Deleted in both or deleted in one and unchanged in the other\n+ if aSha:\n+ print 'Removing ' + path\n+ removeFile(True, path)\n+ else:\n+ # Deleted in one and changed in the other\n+ cleanMerge = False\n+ if not aSha:\n+ print 'CONFLICT (del/mod): \"' + path + '\" deleted in', \\\n+ branch1Name, 'and modified in', branch2Name, \\\n+ '. Version', branch2Name, ' of \"' + path + \\\n+ '\" left in tree'\n+ mode = bMode\n+ sha = bSha\n+ else:\n+ print 'CONFLICT (mod/del): \"' + path + '\" deleted in', \\\n+ branch2Name, 'and modified in', branch1Name + \\\n+ '. Version', branch1Name, 'of \"' + path + \\\n+ '\" left in tree'\n+ mode = aMode\n+ sha = aSha\n+\n+ updateFile(False, sha, mode, path)\n+ \n+ elif (not oSha and aSha and not bSha) or \\\n+ (not oSha and not aSha and bSha):\n+ #\n+ # Case B: Added in one.\n+ #\n+ if aSha:\n+ addBranch = branch1Name\n+ otherBranch = branch2Name\n+ mode = aMode\n+ sha = aSha\n+ conf = 'file/dir'\n+ else:\n+ addBranch = branch2Name\n+ otherBranch = branch1Name\n+ mode = bMode\n+ sha = bSha\n+ conf = 'dir/file'\n+ \n+ if path in dirs:\n+ cleanMerge = False\n+ newPath = uniquePath(path, addBranch)\n+ print 'CONFLICT (' + conf + \\\n+ '): There is a directory with name \"' + path + '\" in', \\\n+ otherBranch + '. Adding \"' + path + '\" as \"' + newPath + '\"'\n+\n+ removeFile(False, path)\n+ path = newPath\n+ else:\n+ print 'Adding \"' + path + '\"'\n+\n+ updateFile(True, sha, mode, path)\n+ \n+ elif not oSha and aSha and bSha:\n+ #\n+ # Case C: Added in both (check for same permissions).\n+ #\n+ if aSha == bSha:\n+ if aMode != bMode:\n+ cleanMerge = False\n+ print 'CONFLICT: File \"' + path + \\\n+ '\" added identically in both branches,'\n+ print 'CONFLICT: but permissions conflict', '0%o' % aMode, \\\n+ '->', '0%o' % bMode\n+ print 'CONFLICT: adding with permission:', '0%o' % aMode\n+\n+ updateFile(False, aSha, aMode, path)\n+ else:\n+ # This case is handled by git-read-tree\n+ assert(False)\n+ else:\n+ cleanMerge = False\n+ newPath1 = uniquePath(path, branch1Name)\n+ newPath2 = uniquePath(path, branch2Name)\n+ print 'CONFLICT (add/add): File \"' + path + \\\n+ '\" added non-identically in both branches.', \\\n+ 'Adding \"' + newPath1 + '\" and \"' + newPath2 + '\" instead.'\n+ removeFile(False, path)\n+ updateFile(False, aSha, aMode, newPath1)\n+ updateFile(False, bSha, bMode, newPath2)\n+\n+ elif oSha and aSha and bSha:\n+ #\n+ # case D: Modified in both, but differently.\n+ #\n+ print 'Auto-merging', path \n+ orig = runProgram(['git-unpack-file', oSha]).rstrip()\n+ src1 = runProgram(['git-unpack-file', aSha]).rstrip()\n+ src2 = runProgram(['git-unpack-file', bSha]).rstrip()\n+ [out, ret] = runProgram(['merge',\n+ '-L', branch1Name + '/' + path,\n+ '-L', 'orig/' + path,\n+ '-L', branch2Name + '/' + path,\n+ src1, orig, src2], returnCode=True)\n+\n+ if aMode == oMode:\n+ mode = bMode\n+ else:\n+ mode = aMode\n+\n+ sha = runProgram(['git-hash-object', '-t', 'blob', '-w',\n+ src1]).rstrip()\n+\n+ if ret != 0:\n+ cleanMerge = False\n+ print 'CONFLICT (content): Merge conflict in \"' + path + '\".'\n+ updateFile(False, sha, mode, path)\n+ else:\n+ updateFile(True, sha, mode, path)\n+\n+ os.unlink(orig)\n+ os.unlink(src1)\n+ os.unlink(src2)\n+ else:\n+ print 'ERROR: Fatal merge failure.'\n+ print \"ERROR: Shouldn't happen\"\n+ sys.exit(1)\n+\n+ return cleanMerge\n+\n+def dropHeads():\n+ try:\n+ os.unlink(os.environ['GIT_DIR'] + '/MERGE_HEAD')\n+ except OSError:\n+ pass\n+\n+ try:\n+ os.unlink(os.environ['GIT_DIR'] + '/LAST_MERGE')\n+ except OSError:\n+ pass\n+\n+def writeHead(head, sha):\n+ if sha[-1] != '\\n':\n+ sha += '\\n'\n+\n+ try:\n+ f = open(os.environ['GIT_DIR'] + '/' + head, 'w')\n+ f.write(sha)\n+ f.close()\n+ except IOError, e:\n+ print 'Failed to write to', os.environ['GIT_DIR'] + '/' + head + ':', \\\n+ e.strerror\n+ sys.exit(1)\n+ return True\n+\n+def checkCleanTree():\n+ [ignore, code] = runProgram(['git-update-cache', '--refresh'],\n+ returnCode = True)\n+ if code != 0:\n+ return False\n+ out = runProgram(['git-diff-cache', '--name-only', '--cached', 'HEAD'])\n+ if len(out) > 0:\n+ return False\n+ return True\n+\n+def doCommit(msg, p1, p2, tree):\n+ assert(isSha(tree))\n+ commit = runProgram(['git-commit-tree', tree, '-p', p1, '-p', p2],\n+ msg + '\\n').rstrip()\n+ assert(isSha(commit))\n+ writeHead('HEAD', commit)\n+ return commit.rstrip()\n+\n+def usage():\n+ print 'Usage:', sys.argv[0], ' '\n+ sys.exit(1)\n+\n+if not checkCleanTree():\n+ print 'Either the cache is out of sync or the working tree does not match HEAD.'\n+ print 'Aborting merge.'\n+ sys.exit(1)\n+\n+setupEnvironment()\n+repoValid()\n+\n+try:\n+ nextArg = 1\n+ if sys.argv[nextArg] == '--write-tree':\n+ alwaysWriteTree = True\n+ nextArg += 1\n+ else:\n+ alwaysWriteTree = False\n+\n+ h1 = firstBranch = sys.argv[nextArg]\n+ nextArg += 1\n+ h2 = secondBranch = sys.argv[nextArg]\n+ nextArg += 1\n+ commitMessage = sys.argv[nextArg]\n+ nextArg += 1\n+except IndexError:\n+ usage()\n+ \n+if len(sys.argv) != nextArg:\n+ usage()\n+\n+print 'Merging', h1, 'with', h2\n+h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()\n+h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()\n+\n+writeHead('ORIG_HEAD', h1)\n+writeHead('LAST_MERGE', h2)\n+\n+graph = buildGraph([h1, h2])\n+\n+[res, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],\n+ firstBranch, secondBranch, graph)\n+\n+print ''\n+\n+if clean:\n+ cmit = doCommit(commitMessage, h1, h2, res.tree())\n+ print 'Committed merge', cmit\n+ print runProgram('git-diff-tree -p ORIG_HEAD ' + cmit + \\\n+ ' | git-apply --stat')\n+ dropHeads()\n+else:\n+ print 'Automatic merge failed, fix up by hand'\n+ writeHead('MERGE_HEAD', h2)\n+\n+if alwaysWriteTree:\n+ print res.tree()\n+\n+if not clean:\n+ sys.exit(1)\ndiff --git a/gitMergeCommon.py b/gitMergeCommon.py\nnew file mode 100644\n--- /dev/null\n+++ b/gitMergeCommon.py\n@@ -0,0 +1,286 @@\n+import sys, re, os, traceback\n+from sets import Set\n+\n+if sys.version_info[0] < 2 or \\\n+ (sys.version_info[0] == 2 and sys.version_info[1] < 4):\n+ print 'Python version 2.4 required, found', \\\n+ str(sys.version_info[0])+'.'+str(sys.version_info[1])+'.'+ \\\n+ str(sys.version_info[2])\n+ sys.exit(1)\n+\n+import subprocess\n+\n+# Debugging machinery\n+# -------------------\n+\n+DEBUG = 0\n+functionsToDebug = Set()\n+\n+def addDebug(func):\n+ if type(func) == str:\n+ functionsToDebug.add(func)\n+ else:\n+ functionsToDebug.add(func.func_name)\n+\n+def debug(*args):\n+ if DEBUG:\n+ funcName = traceback.extract_stack()[-2][2]\n+ if funcName in functionsToDebug:\n+ printList(args)\n+\n+def printList(list):\n+ for x in list:\n+ sys.stdout.write(str(x))\n+ sys.stdout.write(' ')\n+ sys.stdout.write('\\n')\n+\n+# Program execution\n+# -----------------\n+\n+class ProgramError(Exception):\n+ def __init__(self, progStr, error):\n+ self.progStr = progStr\n+ self.error = error\n+\n+addDebug('runProgram')\n+def runProgram(prog, input=None, returnCode=False, env=None, pipeOutput=True):\n+ debug('runProgram prog:', str(prog), 'input:', str(input))\n+ if type(prog) is str:\n+ progStr = prog\n+ else:\n+ progStr = ' '.join(prog)\n+ \n+ try:\n+ if pipeOutput:\n+ stderr = subprocess.STDOUT\n+ stdout = subprocess.PIPE\n+ else:\n+ stderr = None\n+ stdout = None\n+ pop = subprocess.Popen(prog,\n+ shell = type(prog) is str,\n+ stderr=stderr,\n+ stdout=stdout,\n+ stdin=subprocess.PIPE,\n+ env=env)\n+ except OSError, e:\n+ debug('strerror:', e.strerror)\n+ raise ProgramError(progStr, e.strerror)\n+\n+ if input != None:\n+ pop.stdin.write(input)\n+ pop.stdin.close()\n+\n+ if pipeOutput:\n+ out = pop.stdout.read()\n+ else:\n+ out = ''\n+\n+ code = pop.wait()\n+ if returnCode:\n+ ret = [out, code]\n+ else:\n+ ret = out\n+ if code != 0 and not returnCode:\n+ debug('error output:', out)\n+ debug('prog:', prog)\n+ raise ProgramError(progStr, out)\n+# debug('output:', out.replace('\\0', '\\n'))\n+ return ret\n+\n+# Git repository validation and initialization\n+# --------------------------------------------\n+\n+def setupEnvironment():\n+ if 'GIT_DIR' not in os.environ:\n+ os.environ['GIT_DIR'] = '.git'\n+\n+ if not os.environ.has_key('GIT_OBJECT_DIRECTORY'):\n+ os.environ['GIT_OBJECT_DIRECTORY'] = os.environ['GIT_DIR'] + '/objects'\n+\n+def repoValid():\n+ if not (os.path.exists(os.environ['GIT_DIR']) and\n+ os.path.exists(os.environ['GIT_DIR'] + '/refs') and\n+ os.path.exists(os.environ['GIT_OBJECT_DIRECTORY']) and\n+ os.path.exists(os.environ['GIT_OBJECT_DIRECTORY'] + '/00')):\n+ print \"Not a Git archive\"\n+ sys.exit(1)\n+\n+# Code for computing common ancestors\n+# -----------------------------------\n+\n+currentId = 0\n+def getUniqueId():\n+ global currentId\n+ currentId += 1\n+ return currentId\n+\n+# The 'virtual' commit objects have SHAs which are integers\n+shaRE = re.compile('^[0-9a-f]{40}$')\n+def isSha(obj):\n+ return (type(obj) is str and bool(shaRE.match(obj))) or \\\n+ (type(obj) is int and obj >= 1)\n+\n+class Commit:\n+ def __init__(self, sha, parents, tree=None):\n+ self.parents = parents\n+ self.firstLineMsg = None\n+ self.children = []\n+\n+ if tree:\n+ tree = tree.rstrip()\n+ assert(isSha(tree))\n+ self._tree = tree\n+\n+ if not sha:\n+ self.sha = getUniqueId()\n+ self.virtual = True\n+ self.firstLineMsg = 'virtual commit'\n+ assert(isSha(tree))\n+ else:\n+ self.virtual = False\n+ self.sha = sha.rstrip()\n+ assert(isSha(self.sha))\n+\n+ def tree(self):\n+ self.getInfo()\n+ assert(self._tree != None)\n+ return self._tree\n+\n+ def shortInfo(self):\n+ self.getInfo()\n+ return str(self.sha) + ' ' + self.firstLineMsg\n+\n+ def __str__(self):\n+ return self.shortInfo()\n+\n+ def getInfo(self):\n+ if self.virtual or self.firstLineMsg != None:\n+ return\n+ else:\n+ info = runProgram(['git-cat-file', 'commit', self.sha])\n+ info = info.split('\\n')\n+ msg = False\n+ for l in info:\n+ if msg:\n+ self.firstLineMsg = l\n+ break\n+ else:\n+ if l.startswith('tree'):\n+ self._tree = l[5:].rstrip()\n+ elif l == '':\n+ msg = True\n+\n+class Graph:\n+ def __init__(self):\n+ self.commits = []\n+ self.shaMap = {}\n+\n+ def addNode(self, node):\n+ assert(isinstance(node, Commit))\n+ self.shaMap[node.sha] = node\n+ self.commits.append(node)\n+ for p in node.parents:\n+ p.children.append(node)\n+ return node\n+\n+ def reachableNodes(self, n1, n2):\n+ res = {}\n+ def traverse(n):\n+ res[n] = True\n+ for p in n.parents:\n+ traverse(p)\n+\n+ traverse(n1)\n+ traverse(n2)\n+ return res\n+\n+ def fixParents(self, node):\n+ for x in range(0, len(node.parents)):\n+ node.parents[x] = self.shaMap[node.parents[x]]\n+\n+# addDebug('buildGraph')\n+def buildGraph(heads):\n+ debug('buildGraph heads:', heads)\n+ for h in heads:\n+ assert(isSha(h))\n+\n+ g = Graph()\n+\n+ out = runProgram(['git-rev-list', '--parents'] + heads)\n+ for l in out.split('\\n'):\n+ if l == '':\n+ continue\n+ shas = l.split(' ')\n+\n+ # This is a hack, we temporarily use the 'parents' attribute\n+ # to contain a list of SHA1:s. They are later replaced by proper\n+ # Commit objects.\n+ c = Commit(shas[0], shas[1:])\n+\n+ g.commits.append(c)\n+ g.shaMap[c.sha] = c\n+\n+ for c in g.commits:\n+ g.fixParents(c)\n+\n+ for c in g.commits:\n+ for p in c.parents:\n+ p.children.append(c)\n+ return g\n+\n+# Write the empty tree to the object database and return its SHA1\n+def writeEmptyTree():\n+ tmpIndex = os.environ['GIT_DIR'] + '/merge-tmp-index'\n+ def delTmpIndex():\n+ try:\n+ os.unlink(tmpIndex)\n+ except OSError:\n+ pass\n+ delTmpIndex()\n+ newEnv = os.environ.copy()\n+ newEnv['GIT_INDEX_FILE'] = tmpIndex\n+ res = runProgram(['git-write-tree'], env=newEnv).rstrip()\n+ delTmpIndex()\n+ return res\n+\n+def addCommonRoot(graph):\n+ roots = []\n+ for c in graph.commits:\n+ if len(c.parents) == 0:\n+ roots.append(c)\n+\n+ superRoot = Commit(sha=None, parents=[], tree=writeEmptyTree())\n+ graph.addNode(superRoot)\n+ for r in roots:\n+ r.parents = [superRoot]\n+ superRoot.children = roots\n+ return superRoot\n+\n+def getCommonAncestors(graph, commit1, commit2):\n+ '''Find the common ancestors for commit1 and commit2'''\n+ assert(isinstance(commit1, Commit) and isinstance(commit2, Commit))\n+\n+ def traverse(start, set):\n+ stack = [start]\n+ while len(stack) > 0:\n+ el = stack.pop()\n+ set.add(el)\n+ for p in el.parents:\n+ if p not in set:\n+ stack.append(p)\n+ h1Set = Set()\n+ h2Set = Set()\n+ traverse(commit1, h1Set)\n+ traverse(commit2, h2Set)\n+ shared = h1Set.intersection(h2Set)\n+\n+ if len(shared) == 0:\n+ shared = [addCommonRoot(graph)]\n+ \n+ res = Set()\n+\n+ for s in shared:\n+ if len([c for c in s.children if c in shared]) == 0:\n+ res.add(s)\n+ return list(res)\n"},{"id":"8167","messageId":"Pine.LNX.4.63.0509071409470.23242@iabervon.org","threadId":"1743","inReplyTo":"20050907164734.GA20198@c165.ib.student.liu.se","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-07T18:33:42Z","receivedAt":"2005-09-07T18:33:42Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 7 Sep 2005, Fredrik Kuivinen wrote:\n\n> Of the 500 merge commits that currently exists in the kernel\n> repository 19 produces non-clean merges with git-merge-script. The\n> four merge cases listed in\n> <20050827014009.GB18880@c165.ib.student.liu.se> are cleanly merged by\n> git-merge-script. Every merge commit which is cleanly merged by\n> git-resolve-script is also cleanly merged by git-merge-script,\n> furthermore the results are identical. There are currently two merges\n> in the kernel repository which are not cleanly merged by\n> git-resolve-script but are cleanly merged by git-merge-script.\n\nIf you use my read-tree and change git-resolve-script to pass all of the \nancestors to it, how does it do? I expect you'll still be slightly ahead, \nbecause we don't (yet) have content merge with multiple ancestors. You \nshould also check the merge that Tony Luck reported, which undid a revert, \nas well as the one that Len Brown reported around the same time which had \nsimilar problems. I think maintainer trees are a much better test for a \nmerge algorithm, because the kernel repository is relatively linear, while \nmaintainers tend more to merge things back and forth.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8168","messageId":"7v1x407min.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"20050907164734.GA20198@c165.ib.student.liu.se","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-07T18:36:48Z","receivedAt":"2005-09-07T18:36:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> I guess the need for this has decreased with Daniel's new read-tree\n> code. Is there any chance of getting this code merged into mainline\n> git?\n\nI do not think Daniel's code decreased anything. The two\nalgorithms are solving the same problem but they do it\ndifferently. There would be cases where multi-base merge would\ngive better results over your base-on-merge-bases merge; and in\nother cases yours would perform better. I'd like to leave what\nmerge strategy to use as an user option, and leave the door open\nfor other merge strategies to emerge later. I know Pasky wants\nto look into pcdv merge and other alternatives.\n\nThis is still off-the-top-of-my-head, but the top-level merge\nentry point for the end user would be just:\n\n git merge \n\nand by default 'git-merge-script' (sorry, I am taking over the\nname of your script for this 'generic driver for underlying\nmerge strategy scripts') would do something like:\n\n - Run 'git-merge-base -a' to find common ancestors.\n\n - If there is one single common ancestor, do what the current\n 'git-resolve-script' does: if fast-forward, declare success\n and exit without touching anything but $GIT_DIR/HEAD;\n otherwise, run read-tree -m 3-way followed by merge-cache,\n and commit with the given message if the merge was clean and\n exit. If the merge was not clean, go on to the next step.\n\n - User preference (maybe $HOME/.git/merge-preference, maybe\n command line option to 'git merge', maybe interactive\n prompting) can specify which complex merge strategies to use.\n we probably would want to be able to say \"try this, that and\n that-over-there in this order\" in the preference. One of the\n strategies could be 'I give up, just exit and sort it out by\n hand'.\n\n - The chosen merge backend, be it the one that uses Daniel's\n multi-base merge or your base-on-merge-bases merge, takes\n over. In any case, the backend should attempt to resolve the\n two heads, and stop at the point just before committing.\n\n - Evaluate how good the merge is by looking at the result from\n the backend at this point, and if it is not good enough,\n reset the working tree back to the pre-merge state and try\n the next backend. The looping code needs a termination\n clause that picks the best result after exhausting the list\n of backends.\n\n - Then, if the merge backend auto-resolved the heads, we\n commit with ; otherwise we exit with\n non-zero status and have the user sort it out.\n\nThe above assumes that (1) we are already doing a reasonable\nthing in simple one-common-ancestor case; (2) it is in the fast\npath and we want the multiple backend code out of it. You could\nthink of the current 'git-resolve-script' code equivalent of\nhaving a single 'complex merge backend' that just 'gives up'.\n\nIf the above is a good user model, we need a couple of interface\nconvention between merge backends and the above driver:\n\n - Some merge backends (like yours) would require that the\n starting tree is clean while others may not care as long as\n the paths involved are clean (i.e. index matches and\n the working file matches index -- the traditional code and\n Daniel's even allow such a working file being different from\n index if it happens to match the merge result). They need to\n be able to say \"declined to merge even though I might do a\n better job than others if given a clean working tree\". Then\n the user can retry the same merge after getting the working\n tree in a clean state. I personally feel that we do not need\n this complexity and it is reasonable to always require the\n starting tree to be clean when the merge is not a\n fast-forward, though.\n\n - When a merge backend finishes, it may leave the working tree\n in a failed merge state. If we were to try different\n backends in the loop to find the best result, we would need\n some way to assign scores to them. The score should be able\n to tell us if the result can be auto-committable or not, and\n if not how bad it is. I think exit status from the backend\n can be used to tell us the former (i.e. exit non-zero if your\n result has conflicts and you do not want your result to be\n committed immediately), and number of cache-dirty entries can\n be used as an indication of how bad it is (i.e. leave the\n paths you know have not been cleanly merged cache-dirty -- do\n not run git-update-cache on them). This is essentially the\n same convention used by the current 'git-resolve-script'.\n\nI think the 'renaming merge heuristics' Linus outlined in\nanother thread will fall naturally into this picture as a merge\nbackend.\n"},{"id":"8190","messageId":"20050908060651.GA22734@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"Pine.LNX.4.63.0509071409470.23242@iabervon.org","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-08T06:06:51Z","receivedAt":"2005-09-08T06:06:51Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Wed, Sep 07, 2005 at 02:33:42PM -0400, Daniel Barkalow wrote:\n> On Wed, 7 Sep 2005, Fredrik Kuivinen wrote:\n> \n> > Of the 500 merge commits that currently exists in the kernel\n> > repository 19 produces non-clean merges with git-merge-script. The\n> > four merge cases listed in\n> > <20050827014009.GB18880@c165.ib.student.liu.se> are cleanly merged by\n> > git-merge-script. Every merge commit which is cleanly merged by\n> > git-resolve-script is also cleanly merged by git-merge-script,\n> > furthermore the results are identical. There are currently two merges\n> > in the kernel repository which are not cleanly merged by\n> > git-resolve-script but are cleanly merged by git-merge-script.\n> \n> If you use my read-tree and change git-resolve-script to pass all of the \n> ancestors to it, how does it do? I expect you'll still be slightly ahead, \n> because we don't (yet) have content merge with multiple ancestors. You \n> should also check the merge that Tony Luck reported, which undid a revert, \n> as well as the one that Len Brown reported around the same time which had \n> similar problems. I think maintainer trees are a much better test for a \n> merge algorithm, because the kernel repository is relatively linear, while \n> maintainers tend more to merge things back and forth.\n\nJunio tested some of the multiple common ancestor cases with your\nversion of read-tree and reported his results in\n<7virxeycod.fsf@assigned-by-dhcp.cox.net>.\n\nThe two cases my algorithm merges cleanly and git-resolve-script do\nnot merge cleanly are 0e396ee43e445cb7c215a98da4e76d0ce354d9d7 and\n0c168775709faa74c1b87f1e61046e0c51ade7f3. Both of them have two common\nancestors. The second one have, as far as I know, not been tested with\nyour read-tree.\n\nThe merge cases reported by Tony Luck and Len Brown are both cleanly\nmerged by my code.\n\nYou are probably right about the maintainer trees. I should have a\nlook at some of them. Do you know any specific repositories with\ninteresting merge cases?\n\n- Fredrik\n"},{"id":"8195","messageId":"4320536D.2010706@citi.umich.edu","threadId":"1743","inReplyTo":"7vvf1cz64l.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-08T15:06:21Z","receivedAt":"2005-09-08T15:06:21Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Junio C Hamano wrote:\n> Chuck Lever writes:\n> \n> \n>>for the past two weeks i've been attempting to replace the active_cache \n>>array with an abstract data type (linked list just as a prototype) in \n>>order to eliminate the need to use memmove() during insertions and \n>>deletions.\n>>\n>>one big win is that the merge algorithm no longer needs to overwrite the \n>>active_cache. you can keep two lists and simply move elements from one \n>>to the other as you do the merge, and then hook the new, merged list \n>>back to the cache head when you're done.\n>>\n>>anyway, i'm at a point where i could use some help and advice if this is \n>>something you think could be useful in the long run.\n> \n> \n> This is interesting.\n> \n> For something like a kernel tree that has around 18k entries, a\n> single memmove will at the worst case move that many pointers,\n> so naturally a list based implementation would perform well for\n> many insertions and deletions. On the other hand, the list\n> based implementation would make it very expensive to find an\n> entry read-only, I suspect, unlike the array based\n> implementation which lets us do binary search.\n\nusing a list was an easy prototype to see what issues there are when \nconverting from an array into an abstract data type. i've created a few \nhelpers that allow me to limit the list implementation changes to \ncache.h, read-cache.c, and read-tree.c; but having these helpers means \nit should be fairly simple to switch to any reasonable data structure. \n(the helper parts are already working and i can post them to the list if \nfolks are interested).\n\nonce the list implementation is working well, i plan to go back and \nreplace it with something more sophisticated which can perform \ninsertion, deletion, and searching efficiently.\n\nin the long run, i see using a balanced tree. that would make \ninsertions and searches quick, and prevent the tree from degenerating \ninto a linked list due to a series of in-order insertions. a splay tree \nmight be even more entertaining, as it always remains balanced, and a \nsearch operation places the found node or insertion point right at the \nroot of the tree.\n\neach node in the tree would represent a unique path, and have references \nto the entries of all four stages, contained in an array. that would \nsimplify several routines in read-cache.c and probably make the merge \nlogic even easier to understand and more efficient.\n\n> I haven't timed it like you did, but my gut feeling is that the\n> most wastage during the merge is coming from having to move\n> entries because we \"insert into\" or \"remove from\" the same\n> active-cache array.\n\nthe merge actually replaces entries in place, so it is already fairly \nefficient. the wastage in the merge case arises from the many list \ninsertions done by read_cache, all of which involve moving some of the \nactive cache array.\n\n> If we allocate a new array and populate it\n> from scratch as we iterate through the paths being merged and\n> replace the active_cache pointer at the very end, we would do\n> much better without going to a linked list implementation, which\n> would penalize the normal read-only case.\n\ni can already tell you that using a separate source and destination data \nstructure during the merge simplifies the logic and makes it easier to \nunderstand. i imagine it will also be easier to maintain and enhance in \nthe long run.\n\n> I think what Daniel\n> did to read-tree recently, still in the proposed updates branch,\n> would make this kind of change far easier to implement.\n\nas i'm new to git development, i wasn't aware of the proposed branch. i \nwill see if i can take a look (or send me a pointer to the list archives \nif he has posted them here).\n\n> I wanted to cc this message to Daniel but your message to me was\n> somehow private so I did not. Please feel free to bring this\n> issue up either with him directly or on the list.\n\ni wanted to assess whether this was a reasonable idea or if there was \nalready work in progress in this area. thanks for your response!\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763-4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668-1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8196","messageId":"Pine.LNX.4.63.0509081101471.23242@iabervon.org","threadId":"1743","inReplyTo":"20050908060651.GA22734@c165.ib.student.liu.se","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-08T15:27:35Z","receivedAt":"2005-09-08T15:27:35Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Thu, 8 Sep 2005, Fredrik Kuivinen wrote:\n\n> On Wed, Sep 07, 2005 at 02:33:42PM -0400, Daniel Barkalow wrote:\n> > On Wed, 7 Sep 2005, Fredrik Kuivinen wrote:\n> > \n> > > Of the 500 merge commits that currently exists in the kernel\n> > > repository 19 produces non-clean merges with git-merge-script. The\n> > > four merge cases listed in\n> > > <20050827014009.GB18880@c165.ib.student.liu.se> are cleanly merged by\n> > > git-merge-script. Every merge commit which is cleanly merged by\n> > > git-resolve-script is also cleanly merged by git-merge-script,\n> > > furthermore the results are identical. There are currently two merges\n> > > in the kernel repository which are not cleanly merged by\n> > > git-resolve-script but are cleanly merged by git-merge-script.\n> > \n> > If you use my read-tree and change git-resolve-script to pass all of the \n> > ancestors to it, how does it do? I expect you'll still be slightly ahead, \n> > because we don't (yet) have content merge with multiple ancestors. You \n> > should also check the merge that Tony Luck reported, which undid a revert, \n> > as well as the one that Len Brown reported around the same time which had \n> > similar problems. I think maintainer trees are a much better test for a \n> > merge algorithm, because the kernel repository is relatively linear, while \n> > maintainers tend more to merge things back and forth.\n> \n> Junio tested some of the multiple common ancestor cases with your\n> version of read-tree and reported his results in\n> <7virxeycod.fsf@assigned-by-dhcp.cox.net>.\n\nOh, right. I'm clearly not paying enough attention here.\n\n> The two cases my algorithm merges cleanly and git-resolve-script do\n> not merge cleanly are 0e396ee43e445cb7c215a98da4e76d0ce354d9d7 and\n> 0c168775709faa74c1b87f1e61046e0c51ade7f3. Both of them have two common\n> ancestors. The second one have, as far as I know, not been tested with\n> your read-tree.\n\nOkay, I'll have to check whether the result I get seems right. I take it \nyour result agrees with what the users actually produced by hand?\n\n> The merge cases reported by Tony Luck and Len Brown are both cleanly\n> merged by my code.\n\nDo they come out correctly? Both of those have cases which cannot be \ndecided correctly with only the ancestor trees, due to one branch \nreverting a patch that was only in one ancestor. The correct result is to \nrevert that patch, but figuring out that requires looking at more trees. I \nthink your algorithm should work for this case, but it would be good to \nhave verification. (IIRC, Len got the correct result while Tony got the \nwrong result and then corrected it later.)\n\n> You are probably right about the maintainer trees. I should have a\n> look at some of them. Do you know any specific repositories with\n> interesting merge cases?\n\nNot especially, except that I would guess that people who have reported \nhitting bad cases would be more likely to have other interesting merges in \ntheir trees. You might also try merging maintainer trees with each other, \nsince it's relatively likely that there would be complicating overlap that \nonly doesn't cause confusion because things get rearranged in -mm. For \nthat matter, I bet you'd get plenty of test cases out of trying to \nreplicate -mm as a git tree.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8198","messageId":"7v7jdrwlih.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"4320536D.2010706@citi.umich.edu","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-08T16:51:34Z","receivedAt":"2005-09-08T16:51:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Chuck Lever writes:\n\n> Junio C Hamano wrote:\n>> Chuck Lever writes:\n>>\n> once the list implementation is working well, i plan to go back and \n> replace it with something more sophisticated which can perform \n> insertion, deletion, and searching efficiently.\n\nWell, what I wanted to see was if we can get away without\nintroducing more sophisticated data structures, which would add\ncomplexity.\n\n>> I haven't timed it like you did, but my gut feeling is that the\n>> most wastage during the merge is coming from having to move\n>> entries because we \"insert into\" or \"remove from\" the same\n>> active-cache array.\n>\n> the merge actually replaces entries in place, so it is already fairly \n> efficient. the wastage in the merge case arises from the many list \n> insertions done by read_cache, all of which involve moving some of the \n> active cache array.\n\nYes, the reading of three trees upfront is probably the culprit\nin your case, and I think that is something Daniel's read-tree\nrewrite can help. I still see some remove_cache_entry_at()\nthere because it works on the active_cache in place, but the\nstructure of the new code should be much easier to make the kind\nof modification we are talking about.\n\n>> I think what Daniel\n>> did to read-tree recently, still in the proposed updates branch,\n>> would make this kind of change far easier to implement.\n>\n> as i'm new to git development, i wasn't aware of the proposed branch. i \n> will see if i can take a look (or send me a pointer to the list archives \n> if he has posted them here).\n\nIf you already have a local copy of git.git repository you work in:\n\n\tgit fetch http://kernel.org/pub/scm/git/git.git +pu:refs/heads/ko-pu\n git checkout -f ko-pu\n\nOtherwise\n\n\tgit clone http://kernel.org/pub/scm/git/git.git peek\n cd peek\n git checkout -f pu\n\nThe interesting change from the mainline is in read-tree.c\n\nYou can browse http://kernel.org/git/ and see commitdiffs in the\n\"pu\" branch if you are not interested in slurping the whole\nproposed updates branch.\n"},{"id":"8199","messageId":"Pine.LNX.4.58.0509081012540.3208@g5.osdl.org","threadId":"1743","inReplyTo":"7v7jdrwlih.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-08T17:19:57Z","receivedAt":"2005-09-08T17:19:57Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 8 Sep 2005, Junio C Hamano wrote:\n> \n> Yes, the reading of three trees upfront is probably the culprit\n> in your case\n\nHowever, note that _most_ tree reading just reads one.\n\nMerges may take half a second, and yes, when I did it, the fact that we \nmove things around in the array is by far the highest cost. But the thing \nis, if merges take half a second, that's still not only damn good, it's \nnot even the most common operation.\n\nYes, the active_cache[] layout as one big array is inconvenient for \nread_tree(), which tends to want to interleave different trees in the \narray and thus forces things to be moved around.\n\nBut remember what the most common use for the index is - it's the \"single \ntree\" case from read_cache(). That's _so_ much more common than \nread_tree() that it's not even funny.\n\nSo the data structure is optimized for a different case than reading in \ntrees. Big deal. That optimization is definitely worth it: it allows us to \ndo the read_cache() with the actual index entries being totally read-only \n(a linked list would have to add a \"next\" pointer to the cache entries and \nnot allow the in-place thing that read_cache() does).\n\n\t\tLinus\n"},{"id":"8200","messageId":"7vy867v46v.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"Pine.LNX.4.58.0509081012540.3208@g5.osdl.org","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-08T17:51:04Z","receivedAt":"2005-09-08T17:51:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> So the data structure is optimized for a different case than reading in \n> trees. Big deal. That optimization is definitely worth it: it allows us to \n> do the read_cache() with the actual index entries being totally read-only \n> (a linked list would have to add a \"next\" pointer to the cache entries and \n> not allow the in-place thing that read_cache() does).\n\nYes, you are right. What is being discussed is to help\nread-tree.c while keeping that nice property.\n\nI think Daniel's patch is going in the right direction. It can\nbe told to populate the resulting cache from scratch by reading\nthe current cache and the trees being read, instead of inserting\nand removing the current cache as it does right now. Once that\nis done, we would not have to do repeated memmove to insert and\ndelete an entry one at a time anymore.\n"},{"id":"8203","messageId":"43207FE6.2030108@citi.umich.edu","threadId":"1743","inReplyTo":"Pine.LNX.4.58.0509081012540.3208@g5.osdl.org","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-08T18:16:06Z","receivedAt":"2005-09-08T18:16:06Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Linus Torvalds wrote:\n> \n> On Thu, 8 Sep 2005, Junio C Hamano wrote:\n> \n>>Yes, the reading of three trees upfront is probably the culprit\n>>in your case\n> \n> \n> However, note that _most_ tree reading just reads one.\n> \n> Merges may take half a second, and yes, when I did it, the fact that we \n> move things around in the array is by far the highest cost. But the thing \n> is, if merges take half a second, that's still not only damn good, it's \n> not even the most common operation.\n\nin my case the merges were taking significantly longer than a half \nsecond. making this change is certainly not worth it if merges are \nrunning fast...\n\n> Yes, the active_cache[] layout as one big array is inconvenient for \n> read_tree(), which tends to want to interleave different trees in the \n> array and thus forces things to be moved around.\n> \n> But remember what the most common use for the index is - it's the \"single \n> tree\" case from read_cache(). That's _so_ much more common than \n> read_tree() that it's not even funny.\n\nread_cache is fast as implemented. the issue is that the next thing \nthat is often done is a cache insert, which requires a memmove, which is \nslow.\n\n> So the data structure is optimized for a different case than reading in \n> trees. Big deal. That optimization is definitely worth it: it allows us to \n> do the read_cache() with the actual index entries being totally read-only \n> (a linked list would have to add a \"next\" pointer to the cache entries and \n> not allow the in-place thing that read_cache() does).\n\nthey are still read-only with my linked list implementation.\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763-4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668-1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8205","messageId":"Pine.LNX.4.58.0509081131070.5940@g5.osdl.org","threadId":"1743","inReplyTo":"43207FE6.2030108@citi.umich.edu","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-08T18:35:53Z","receivedAt":"2005-09-08T18:35:53Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 8 Sep 2005, Chuck Lever wrote:\n> \n> in my case the merges were taking significantly longer than a half \n> second. making this change is certainly not worth it if merges are \n> running fast...\n\nNote that in cold-cache cases, all the expense of read-tree is in actually\nreading the tree objects themselves (a kernel tree has more than a\nthousand subdirectories). Also, a full \"git pull\" will do the diffstat \netc, and then the expense ends up being in the actual \"git diff\" part.\n\nSo read-tree itself may be half a second, but a merge ends up having other \nparts.\n\n> they are still read-only with my linked list implementation.\n\nBtw, in the sparse project, we have this really smart \"pointer list\" data\nstructure, which is extremely space- and time-efficient. It ends up\n_looking_ like a linked list, but it batches things up in hunks of 29\nentries (29 pointers plus overhead gives you blocks of 32 longwords, which\nis the allocation size) and thus gives basically a cache-friendly\ndoubly-linked list. It knows how to do insertions, traversals etc very \nefficiently.\n\nAny interest?\n\n\t\tLinus\n"},{"id":"8207","messageId":"432089D8.4060507@citi.umich.edu","threadId":"1743","inReplyTo":"Pine.LNX.4.58.0509081131070.5940@g5.osdl.org","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-08T18:58:32Z","receivedAt":"2005-09-08T18:58:32Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Linus Torvalds wrote:\n> \n> On Thu, 8 Sep 2005, Chuck Lever wrote:\n> \n>>in my case the merges were taking significantly longer than a half \n>>second. making this change is certainly not worth it if merges are \n>>running fast...\n> \n> \n> Note that in cold-cache cases, all the expense of read-tree is in actually\n> reading the tree objects themselves (a kernel tree has more than a\n> thousand subdirectories). Also, a full \"git pull\" will do the diffstat \n> etc, and then the expense ends up being in the actual \"git diff\" part.\n> \n> So read-tree itself may be half a second, but a merge ends up having other \n> parts.\n\ni measured this using the following test...\n\ni have a linux kernel git repository under control of stgit and it has \nabout 70 patches in it. i did an \"stg status\" to heat the page cache. \ni popped all the patches, then did an \"stg pull origin\".\n\ni started oprofile, and did an \"stg push -a\". it took about 9 minutes.\n\ni stopped oprofile and looked at the results. roughly 65% of the total \nCPU time was spent in libc:memmove. after instrumenting git, i \ndetermined that in the \"stg push\" case the critical memmove was the one \nin add_cache_entry.\n\nnote that i'm not saying that the 9 minutes of wall clock time was \nentirely due to CPU... catalin has been steadily improving \"stg push\" so \nthis time has shortened by more than half, recently. but i do notice \nthat working in a kernel repository is significantly slower than working \nin my git or stgit source repositories, which are smaller by far. the \nsmall repositories behave just as i expect, the tools respond quite \nsnappily.\n\n>>they are still read-only with my linked list implementation.\n> \n> Btw, in the sparse project, we have this really smart \"pointer list\" data\n> structure, which is extremely space- and time-efficient. It ends up\n> _looking_ like a linked list, but it batches things up in hunks of 29\n> entries (29 pointers plus overhead gives you blocks of 32 longwords, which\n> is the allocation size) and thus gives basically a cache-friendly\n> doubly-linked list. It knows how to do insertions, traversals etc very \n> efficiently.\n> \n> Any interest?\n\ni'm not married to splay trees. i think we should explore several \ndifferent data structures before picking one, and this one sounds \nreasonable to try.\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763-4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668-1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8208","messageId":"20050908200559.GA26088@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"Pine.LNX.4.63.0509081101471.23242@iabervon.org","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-08T20:05:59Z","receivedAt":"2005-09-08T20:05:59Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Thu, Sep 08, 2005 at 11:27:35AM -0400, Daniel Barkalow wrote:\n\n...\n\n> > The two cases my algorithm merges cleanly and git-resolve-script do\n> > not merge cleanly are 0e396ee43e445cb7c215a98da4e76d0ce354d9d7 and\n> > 0c168775709faa74c1b87f1e61046e0c51ade7f3. Both of them have two common\n> > ancestors. The second one have, as far as I know, not been tested with\n> > your read-tree.\n> \n> Okay, I'll have to check whether the result I get seems right. I take it \n> your result agrees with what the users actually produced by hand?\n \nThe first one agrees with what was actually committed. For the second\none the difference between the tree produced by the algorithm and what\nwas committed is:\n\ndiff --git a/include/net/ieee80211.h b/include/net/ieee80211.h\n--- a/include/net/ieee80211.h\n+++ b/include/net/ieee80211.h\n@@ -425,9 +425,7 @@ struct ieee80211_stats {\n \n struct ieee80211_device;\n \n-#if 0 /* for later */\n #include \"ieee80211_crypt.h\"\n-#endif\n \n #define SEC_KEY_1 (1<<0)\n #define SEC_KEY_2 (1<<1)\n\n\nI have looked at the files and common ancestors involved and I think\nthat this change have been introduced manually. I may have missed\nsomething when I analysed it though...\n\n\n> > The merge cases reported by Tony Luck and Len Brown are both cleanly\n> > merged by my code.\n> \n> Do they come out correctly? Both of those have cases which cannot be \n> decided correctly with only the ancestor trees, due to one branch \n> reverting a patch that was only in one ancestor. The correct result is to \n> revert that patch, but figuring out that requires looking at more trees. I \n> think your algorithm should work for this case, but it would be good to \n> have verification. (IIRC, Len got the correct result while Tony got the \n> wrong result and then corrected it later.)\n\nLen's merge case come out identically to the tree he committed. I have\ndescribed what I got for Tony's case in\n<20050826184731.GA13629@c165.ib.student.liu.se> (my merge algorithm\nproduces the result Tony expected to get, but he didn't get that from\ngit-resolve-script).\n\n- Fredrik\n"},{"id":"8211","messageId":"7v4q8vuvom.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"7v1x407min.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-08T20:54:49Z","receivedAt":"2005-09-08T20:54:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> ... I'd like to leave what\n> merge strategy to use as an user option, and leave the door open\n> for other merge strategies to emerge later. I know Pasky wants\n> to look into pcdv merge and other alternatives.\n>\n> This is still off-the-top-of-my-head, but the top-level merge\n> entry point for the end user would be just:\n>\n> git merge \n>\n> and by default 'git-merge-script' (sorry, I am taking over the\n> name of your script for this 'generic driver for underlying\n> merge strategy scripts') would do something like:\n\nAnd here is \"an illustration of concept\" patch, requesting for\ncomments. It probably is buggy as h*ll, but I am showing\ninterfaces early, hoping this is something people can agree on\nto use to plug various merge strategies into.\n\nThe patch uses 'git-show-branches --merge-base' as an improved\n'git-merge-base -a' that can do more than two heads, which still\nonly exists in my development repository, but I hope you get the\nidea.\n\n------------\nSubject: [PATCH] Multi-backend merge driver.\n\nThis is just an illustration of concept patch.\n\nThe new command 'git merge' takes the current head and one or more\nremote heads, with the commit log message for the automated case.\n\nIf the heads being merged are simple fast-forwards, it acts the\nsame way as the current 'git resolve'. Otherwise, it tries\ndifferent merge strategies and takes the result from the one that\nsucceeded auto-merging, if there is any.\n\nIf no merge strategy succeeds auto-merging, their results are\nevaluated for number of paths needed for hand resolving, and the\none with the least number of such paths is left in the working\ntree. The user is asked to resolve them by hand and make a\ncommit manually.\n\nThe calling convention from the 'git merge' driver to merge\nstrategy programs is very simple:\n\n - A strategy program is to be called 'git-merge-'.\n\n - They take input of this form:\n\n\t ... '--' ...\n\n That is, one or more the common ancestors, double dash, the\n current head, and one or more remote heads being merged into\n the current branch.\n\n - Before a strategy program is called, the working tree is\n matched to the current .\n\n - The strategy program exits with status code 0 when it\n successfully auto-merges the given heads. It should do\n update-cache for all the merged paths when it does so -- the\n index file will be used to record the merge result as a\n commit by the driver.\n\n - The strategy program exits with status code 1 when it leaves\n conflicts behind. It should do update-cache for all the\n merged paths that it successfully auto-merged, and leave the\n cache entry in the index file as the same as for paths\n it could not auto-merge, and leave its best-effort result\n with conflict markers in the working tree when it does so.\n\n - The strategy program exists with status code other than 0 or\n 1 if it does not handle the given merge at all.\n\nAs examples, this commit comes with merge strategies based on\n'git resolve' and 'git octopus'.\n\nSigned-off-by: Junio C Hamano \n\n---\n\n git-commit.sh | 2 \n git-merge-octopus.sh | 86 +++++++++++++++++++++\n git-merge-resolve.sh | 80 ++++++++++++++++++++\n git-merge.sh | 205 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 372 insertions(+), 1 deletions(-)\n create mode 100755 git-merge-octopus.sh\n create mode 100755 git-merge-resolve.sh\n create mode 100755 git-merge.sh\n\na65a614ce7f67c3ed4dee3bed3ab4d86d3f79577\ndiff --git a/git-commit.sh b/git-commit.sh\n--- a/git-commit.sh\n+++ b/git-commit.sh\n@@ -158,7 +158,7 @@ if [ ! -r \"$GIT_DIR/HEAD\" ]; then\n \tPARENTS=\"\"\n else\n \tif [ -f \"$GIT_DIR/MERGE_HEAD\" ]; then\n-\t\tPARENTS=\"-p HEAD -p MERGE_HEAD\"\n+\t\tPARENTS=\"-p HEAD \"`sed -e 's/^/-p /' \"$GIT_DIR/MERGE_HEAD\"`\n \tfi\n \tif test \"$use_commit\" != \"\"\n \tthen\ndiff --git a/git-merge-octopus.sh b/git-merge-octopus.sh\nnew file mode 100755\n--- /dev/null\n+++ b/git-merge-octopus.sh\n@@ -0,0 +1,86 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2005 Junio C Hamano\n+#\n+# Resolve two or more trees.\n+#\n+\n+# The first parameters up to -- are merge bases; the rest are heads.\n+bases= head= remotes= sep_seen=\n+for arg\n+do\n+\tcase \",$sep_seen,$head,$arg,\" in\n+\t*,--,)\n+\t\tsep_seen=yes\n+\t\t;;\n+\t,yes,,*)\n+\t\thead=$arg\n+\t\t;;\n+\t,yes,*)\n+\t\tremotes=\"$remotes$arg \"\n+\t\t;;\n+\t*)\n+\t\tbases=\"$bases$arg \"\n+\t\t;;\n+\tesac\n+done\n+\n+# Reject if this is not an Octopus -- resolve should be used instead.\n+case \"$remotes\" in\n+?*' '?*)\n+\t;;\n+*)\n+\texit 2 ;;\n+esac\n+\n+# MRC is the current \"merge reference commit\"\n+# MRT is the current \"merge result tree\"\n+\n+MRC=$head MSG= PARENT=\"-p $head\"\n+MRT=$(git-write-tree)\n+CNT=1 ;# counting our head\n+NON_FF_MERGE=0\n+for SHA1 in $remotes\n+do\n+\tcommon=$(git-merge-base $MRC $SHA1) ||\n+\t\tdie \"Unable to find common commit with $SHA1\"\n+\n+\tif test \"$common\" = $SHA1\n+\tthen\n+\t\techo \"Already up-to-date with $SHA1\"\n+\t\tcontinue\n+\tfi\n+\n+\tCNT=`expr $CNT + 1`\n+\tPARENT=\"$PARENT -p $SHA1\"\n+\n+\tif test \"$common,$NON_FF_MERGE\" = \"$MRC,0\"\n+\tthen\n+\t\t# The first head being merged was a fast-forward.\n+\t\t# Advance MRC to the head being merged, and use that\n+\t\t# tree as the intermediate result of the merge.\n+\t\t# We still need to count this as part of the parent set.\n+\n+\t\techo \"Fast forwarding to: $SHA1\"\n+\t\tgit-read-tree -u -m $head $SHA1 || exit\n+\t\tMRC=$SHA1 MRT=$(git-write-tree)\n+\t\tcontinue\n+\tfi\n+\n+\tNON_FF_MERGE=1\n+\n+\techo \"Trying simple merge with $SHA1\"\n+\tgit-read-tree -u -m $common $MRT $SHA1 || exit 2\n+\tnext=$(git-write-tree 2>/dev/null)\n+\tif test $? -ne 0\n+\tthen\n+\t\techo \"Simple merge did not work, trying automatic merge.\"\n+\t\tgit-merge-index -o git-merge-one-file -a ||\n+\t\texit 2 ; # Automatic merge failed; should not be doing Octopus\n+\t\tnext=$(git-write-tree 2>/dev/null)\n+\tfi\n+\tMRC=$common\n+\tMRT=$next\n+done\n+\n+exit 0\ndiff --git a/git-merge-resolve.sh b/git-merge-resolve.sh\nnew file mode 100755\n--- /dev/null\n+++ b/git-merge-resolve.sh\n@@ -0,0 +1,80 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2005 Linus Torvalds\n+#\n+# Resolve two trees.\n+\n+# The first parameters up to -- are merge bases; the rest are heads.\n+bases= head= remotes= sep_seen=\n+for arg\n+do\n+\tcase \",$sep_seen,$head,$arg,\" in\n+\t*,--,)\n+\t\tsep_seen=yes\n+\t\t;;\n+\t,yes,,*)\n+\t\thead=$arg\n+\t\t;;\n+\t,yes,*)\n+\t\tremotes=\"$remotes$arg \"\n+\t\t;;\n+\t*)\n+\t\tbases=\"$bases$arg \"\n+\t\t;;\n+\tesac\n+done\n+\n+# Give up if we are given more than two remotes -- not handling octopus.\n+case \"$remotes\" in\n+?*' '?*)\n+\texit 2 ;;\n+esac\n+\n+# Find an optimum merge base if there are more than one candidates.\n+case \"$bases\" in\n+?*' '?*)\n+\techo \"Trying to find the optimum merge base.\"\n+\tG=.tmp-index$$\n+\tbest=\n+\tbest_cnt=-1\n+\tfor c in $bases\n+\tdo\n+\t\trm -f $G\n+\t\tGIT_INDEX_FILE=$G git-read-tree -m $c $head $remotes \\\n+\t\t\t 2>/dev/null ||\tcontinue\n+\t\t# Count the paths that are unmerged.\n+\t\tcnt=`GIT_INDEX_FILE=$G git-ls-files --unmerged | wc -l`\n+\t\tif test $best_cnt -le 0 -o $cnt -le $best_cnt\n+\t\tthen\n+\t\t\tbest=$c\n+\t\t\tbest_cnt=$cnt\n+\t\t\tif test \"$best_cnt\" -eq 0\n+\t\t\tthen\n+\t\t\t\t# Cannot do any better than all trivial merge.\n+\t\t\t\tbreak\n+\t\t\tfi\n+\t\tfi\n+\tdone\n+\trm -f $G\n+\tcommon=\"$best\"\n+\t;;\n+*)\n+\tcommon=\"$bases\"\n+\t;;\n+esac\n+\n+git-update-index --refresh 2>/dev/null\n+git-read-tree -u -m $common $head $remotes || exit 2\n+echo \"Trying simple merge.\"\n+if result_tree=$(git-write-tree 2>/dev/null)\n+then\n+\texit 0\n+else\n+\techo \"Simple merge failed, trying Automatic merge.\"\n+\tif git-merge-index -o git-merge-one-file -a\n+\tthen\n+\t\texit 0\n+\telse\n+\t\texit 1\n+\tfi\n+fi\ndiff --git a/git-merge.sh b/git-merge.sh\nnew file mode 100755\n--- /dev/null\n+++ b/git-merge.sh\n@@ -0,0 +1,205 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2005 Junio C Hamano\n+#\n+\n+. git-sh-setup || die \"Not a git archive\"\n+\n+LF='\n+'\n+\n+usage () {\n+ die \"git-merge [-n] [-s ]... +\"\n+}\n+\n+# all_strategies='resolve barkarow fredrik octopus'\n+\n+all_strategies='resolve octopus'\n+default_strategies='resolve octopus'\n+use_strategies=\n+\n+dropheads() {\n+\trm -f -- \"$GIT_DIR/MERGE_HEAD\" || exit 1\n+}\n+\n+summary() {\n+\tcase \"$no_summary\" in\n+\t'')\n+\t\tgit-diff-tree -p -M $head \"$1\" |\n+\t\tgit-apply --stat --summary\n+\t\t;;\n+\tesac\n+}\n+\n+while case \"$#\" in 0) break ;; esac\n+do\n+\tcase \"$1\" in\n+\t-n|--n|--no|--no-|--no-s|--no-su|--no-sum|--no-summ|\\\n+\t\t--no-summa|--no-summar|--no-summary)\n+\t\tno_summary=t ;;\n+\t-s=*|--s=*|--st=*|--str=*|--stra=*|--strat=*|--strate=*|\\\n+\t\t--strateg=*|--strategy=*|\\\n+\t-s|--s|--st|--str|--stra|--strat|--strate|--strateg|--strategy)\n+\t\tcase \"$#,$1\" in\n+\t\t*,*=*)\n+\t\t\tstrategy=`expr \"$1\" : '-[^=]*=\\(.*\\)'` ;;\n+\t\t0,*)\n+\t\t\tusage ;;\n+\t\t*)\n+\t\t\tstrategy=\"$2\"\n+\t\t\tshift ;;\n+\t\tesac\n+\t\tcase \" $all_strategies \" in\n+\t\t*\" $strategy \"*)\n+\t\t\tuse_strategies=\"$use_strategies$strategy \" ;;\n+\t\t*)\n+\t\t\tdie \"available strategies are: $all_strategies\" ;;\n+\t\tesac\n+\t\t;;\n+\t-*)\tusage ;;\n+\t*)\tbreak ;;\n+\tesac\n+\tshift\n+done\n+\n+case \"$use_strategies\" in\n+'')\n+\tuse_strategies=$default_strategies\n+\t;;\n+esac\n+test \"$#\" -le 2 && usage ;# we need at least two heads.\n+\n+merge_msg=\"$1\"\n+shift\n+head=$(git-rev-parse --verify \"$1\"^0) || usage\n+shift\n+\n+# All the rest are remote heads\n+for remote\n+do\n+\tgit-rev-parse --verify \"$remote'^0 >/dev/null ||\n+\t die \"$remote - not something we can merge\"\n+done\n+\n+common=$(git-show-branch --merge-base $head \"$@\")\n+echo \"$head\" >\"$GIT_DIR/ORIG_HEAD\"\n+\n+case \"$#,$common\" in\n+*,'')\n+\tdie \"Unable to find common commit between $head and $*\"\n+\t;;\n+1,\"$1\")\n+\t# If head can reach all the merge then we are up to date.\n+\t# but first the most common case of merging one remote\n+\techo \"Already up-to-date. Yeeah!\"\n+\tdropheads\n+\texit 0\n+\t;;\n+1,\"$head\")\n+\t# Again the most common case of merging one remote.\n+\techo \"Updating from $head to $1.\"\n+\tgit-update-index --refresh 2>/dev/null\n+\tgit-read-tree -u -m $head \"$1\" || exit 1\n+\techo \"$1\" > \"$GIT_DIR/HEAD\"\n+\tsummary \"$1\"\n+\tdropheads\n+\texit 0\n+\t;;\n+1,*)\n+\t# We are not doing octopus and not fast forward. Need a\n+\t# real merge.\n+\t;;\n+*)\n+\t# An octopus. If we can reach all the remote we are up to date.\n+\tup_to_date=t\n+\tfor remote\n+\tdo\n+\t\tcommon_one=$(git-merge-base $head $remote)\n+\t\tif test \"$common_one\" != \"$remote\"\n+\t\tthen\n+\t\t\tup_to_date=f\n+\t\t\tbreak\n+\t\tfi\n+\tdone\n+\tif test \"$up_to_date\" = t\n+\tthen\n+\t\techo \"Already up-to-date. Yeeah!\"\n+\t\tdropheads\n+\t\texit 0\n+\tfi\n+\t;;\n+esac\n+\n+# At this point we need a real merge. Require that the tree matches\n+# exactly our head.\n+\n+git-update-index --refresh &&\n+test '' = `git-diff-index --cache --name-only $head` || {\n+\tdie \"Need real merge but the working tree has local changes.\"\n+}\n+\n+result_tree= best_cnt=-1 best_strategy= wt_strategy=\n+for strategy in $use_strategies\n+do\n+ test \"$wt_strategy\" = '' || git reset --hard $head\n+\n+ echo \"Trying merge strategy $strategy...\"\n+ wt_strategy=$strategy\n+ git-merge-$strategy $common -- $head \"$@\" || {\n+\n+\t# The backend exits with 1 when conflicts are left to be resolved,\n+\t# with 2 when it does not handle the given merge at all.\n+\n+\tcase \"$?\" in\n+\t1)\n+\t cnt=`git-diff-files --name-only | wc -l`\n+\t if test $best_cnt -le 0 -o $cnt -le $best_cnt\n+\t then\n+\t\tbest_strategy=$strategy\n+\t\tbest_cnt=$cnt\n+\t fi\n+\tesac\n+\tcontinue\n+ }\n+\n+ # Automerge succeeded.\n+ result_tree=$(git-write-tree) && break\n+done\n+\n+# If we have a resulting tree, that means the strategy module\n+# auto resolved the merge cleanly.\n+if test '' != $result_tree\n+then\n+ parents=\"-p $head\"\n+ for remote\n+ do\n+ parents=\"$parents -p $remote\"\n+ done\n+ result_commit=$(echo \"$merge_msg\" | git-commit-tree $result_tree $parents)\n+ echo \"Committed merge $result_commit, made by $wt_strategy.\"\n+ echo $result_commit >\"$GIT_DIR\"/HEAD\n+ summary $result_commit\n+ dropheads\n+ exit 0\n+fi\n+\n+# Pick the result from the best strategy and have the user fix it up.\n+case \"$best_strategy\" in\n+'')\n+\tgit reset --hard $head\n+\tdie \"No merge strategy handled the merge.\"\n+\t;;\n+\"$wt_strategy\")\n+\t# We already have its result in the working tree.\n+\t;;\n+*)\n+\techo \"Using the $strategy to prepare resolving by hand.\"\n+\tgit reset --hard $head\n+\tgit-merge-$best_strategy $common -- $head \"$@\"\n+\t;;\n+esac\n+for remote\n+do\n+\techo $remote\n+done >\"$GIT_DIR/MERGE_HEAD\"\n+die \"Automatic merge failed; fix up by hand\"\n"},{"id":"8212","messageId":"Pine.LNX.4.58.0509081357480.3039@g5.osdl.org","threadId":"1743","inReplyTo":"432089D8.4060507@citi.umich.edu","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-08T20:59:54Z","receivedAt":"2005-09-08T20:59:54Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 8 Sep 2005, Chuck Lever wrote:\n> > \n> > Btw, in the sparse project, we have this really smart \"pointer list\" data\n> > structure, which is extremely space- and time-efficient. It ends up\n> > _looking_ like a linked list, but it batches things up in hunks of 29\n> > entries (29 pointers plus overhead gives you blocks of 32 longwords, which\n> > is the allocation size) and thus gives basically a cache-friendly\n> > doubly-linked list. It knows how to do insertions, traversals etc very \n> > efficiently.\n> > \n> > Any interest?\n> \n> i'm not married to splay trees. i think we should explore several \n> different data structures before picking one, and this one sounds \n> reasonable to try.\n\nActually, I just realized that one of the issues is just plain looking up\na name (ie \"pos = cache_name_pos(..)\", and the sparse list don't make that\nvery efficient unless you have a good starting point.\n\nSo a splay tree is probably more appropriate.\n\n\t\t\tLinus\n"},{"id":"8214","messageId":"4320ABCD.1060803@gmail.com","threadId":"1743","inReplyTo":"7v4q8vuvom.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2005-09-08T21:23:25Z","receivedAt":"2005-09-08T21:23:25Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Junio C Hamano wrote:\n[...]\n> Subject: [PATCH] Multi-backend merge driver.\n> \n> This is just an illustration of concept patch.\n> \n> The new command 'git merge' takes the current head and one or more\n> remote heads, with the commit log message for the automated case.\n> \n> If the heads being merged are simple fast-forwards, it acts the\n> same way as the current 'git resolve'. Otherwise, it tries\n> different merge strategies and takes the result from the one that\n> succeeded auto-merging, if there is any.\n> \n> If no merge strategy succeeds auto-merging, their results are\n> evaluated for number of paths needed for hand resolving, and the\n> one with the least number of such paths is left in the working\n> tree. The user is asked to resolve them by hand and make a\n> commit manually.\n[...]\n\nThis last paragraph concerns me because it limits us to a very simple \nmetric, \"number of paths needed for hand resolving\". Some \"hand \nresolving\" situations can be more complex than others and it would nice \nto use that information if it was available.\n\nOf course I have no idea what that information may be or how it can be \ncomputed.\n"},{"id":"8213","messageId":"Pine.LNX.4.63.0509081723360.23242@iabervon.org","threadId":"1743","inReplyTo":"20050908200559.GA26088@c165.ib.student.liu.se","subject":"Re: [PATCH 0/2] A new merge algorithm, take 3","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-08T21:27:16Z","receivedAt":"2005-09-08T21:27:16Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Thu, 8 Sep 2005, Fredrik Kuivinen wrote:\n\n> The first one agrees with what was actually committed. For the second\n> one the difference between the tree produced by the algorithm and what\n> was committed is:\n> \n> diff --git a/include/net/ieee80211.h b/include/net/ieee80211.h\n> --- a/include/net/ieee80211.h\n> +++ b/include/net/ieee80211.h\n> @@ -425,9 +425,7 @@ struct ieee80211_stats {\n> \n> struct ieee80211_device;\n> \n> -#if 0 /* for later */\n> #include \"ieee80211_crypt.h\"\n> -#endif\n> \n> #define SEC_KEY_1 (1<<0)\n> #define SEC_KEY_2 (1<<1)\n> \n> \n> I have looked at the files and common ancestors involved and I think\n> that this change have been introduced manually. I may have missed\n> something when I analysed it though...\n\nCertainly possible that it was done manually.\n\n> > > The merge cases reported by Tony Luck and Len Brown are both cleanly\n> > > merged by my code.\n> > \n> > Do they come out correctly? Both of those have cases which cannot be \n> > decided correctly with only the ancestor trees, due to one branch \n> > reverting a patch that was only in one ancestor. The correct result is to \n> > revert that patch, but figuring out that requires looking at more trees. I \n> > think your algorithm should work for this case, but it would be good to \n> > have verification. (IIRC, Len got the correct result while Tony got the \n> > wrong result and then corrected it later.)\n> \n> Len's merge case come out identically to the tree he committed. I have\n> described what I got for Tony's case in\n> <20050826184731.GA13629@c165.ib.student.liu.se> (my merge algorithm\n> produces the result Tony expected to get, but he didn't get that from\n> git-resolve-script).\n\nGood. It looks to me like this is a good algorithm in practice, then.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8228","messageId":"7v3boen0rb.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"432089D8.4060507@citi.umich.edu","subject":"[RFH] Merge driver","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-09T07:44:40Z","receivedAt":"2005-09-09T07:44:40Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I have several requests to people who are interested in merges\nand read-tree changes.\n\nI am pretty much set to use the recent read-tree updates Daniel\nhas been working on. The only reason it has not hit the\n\"master\" branch yet, except that it still has known leaks that\nhave not been plugged, is because read-tree is so fundamental to\neverything we do, and I am trying to be extremely conservative\nhere. I've beaten it myself reasonably well and have not found\nany regressions (except removal of --emu23 which I believe\nnobody uses anyway), but I'd appreciate people to try it out and\nsee if it performs well for your dataset.\n\nIf you are planning further surgery on read-tree code, please\nbase your changes on Daniel's rewrite to avoid your effort being\nwasted. This request goes both to Chuck (active_cache\nabstraction) and Fredrik (addition of 'ignore index and working\ntree matching rules' [*1*]).\n\nA proposed merge driver 'git-merge' is in the proposed updates\nbranch. This is intended to be the top-level user interface to\nthe merge machinery which drives multiple merge strategy\nscripts, and I am hoping that I can eventually (1) retire\n'git-resolve' and 'git-octopus' (they simply become merge\nstrategy scripts driven by 'git-merge') and (2) call 'git-merge'\nfrom 'git-pull'. What I have in the proposed updates branch has\nbeen fixed since my earlier message to the list and has a new\nmerge strategy script, in addition to 'resolve' and 'octopus',\ncalled 'git-merge-multibase'. This uses Daniel's read-tree that\ncan use more than one merge bases. I request Daniel to give OK\nto its name or suggest a better name for this script -- I would\neven accept 'git-merge-barkalow' if you want ;-).\n\nIf you are planning to implement a new merge strategy, please\nuse the ones in the proposed updates branch as examples, and\ncomplain and suggest improvements if you find the interface\nbetween the strategy scripts and the driver lacking. This\nrequest goes primarily to Fredrik. I'm interested in doing the\nrenaming merge that would have helped HPA's klibc-kbuild vs\nklibc case myself but if somebody else is so inclined please go\nwild.\n\nAnd finally, a request to everybody; please try out 'git-merge'\nand see how you like it.\n\n`git-merge` [-n] [-s ]... ...\n\n-n::\n\tDo not show diffstat at the end of the merge.\n\n-s ::\n\tuse that merge strategy; can be given more than once to\n\tspecify them in the order they should be tried. If\n\tthere is no `-s` option, built-in list of strategies is\n\tused instead.\n\n::\n\tour branch head commit.\n\n::\n\tother branch head merged into our branch. You need at\n\tleast one . Specifying more than one \n\tobviously means you are trying an Octopus.\n\nHere is a sample transcript from a test resolving one of the\n'more-than-one-merge-base' commits Fredrik found in the kernel\nrepository (\": siamese;\" is my $PS1; \" \" is my $PS2).\n\n : siamese; git reset --hard b8112df71cae7d6a86158caeb19d215f56c4f9ab\n : siamese; git merge -n \\\n 'reproduce 0e396ee43e445cb7c215a98da4e76d0ce354d9d7' \\\n HEAD 2089a0d38bc9c2cdd084207ebf7082b18cf4bf58\n Trying merge strategy resolve...\n Trying to find the optimum merge base.\n Trying simple merge.\n Simple merge failed, trying Automatic merge.\n Removing drivers/net/fmv18x.c\n Auto-merging drivers/net/r8169.c.\n merge: warning: conflicts during merge\n ERROR: Merge conflict in drivers/net/r8169.c.\n Removing drivers/net/sk_g16.c\n Removing drivers/net/sk_g16.h\n fatal: merge program failed\n Rewinding the tree to pristine...\n Trying merge strategy multibase...\n Trying simple merge.\n Simple merge failed, trying Automatic merge.\n Removing drivers/net/fmv18x.c\n Auto-merging drivers/net/r8169.c.\n merge: warning: conflicts during merge\n ERROR: Merge conflict in drivers/net/r8169.c.\n Removing drivers/net/sk_g16.c\n Removing drivers/net/sk_g16.h\n fatal: merge program failed\n Rewinding the tree to pristine...\n Trying merge strategy octopus...\n Rewinding the tree to pristine...\n Using the multibase to prepare resolving by hand.\n Trying simple merge.\n Simple merge failed, trying Automatic merge.\n Removing drivers/net/fmv18x.c\n Auto-merging drivers/net/r8169.c.\n merge: warning: conflicts during merge\n ERROR: Merge conflict in drivers/net/r8169.c.\n Removing drivers/net/sk_g16.c\n Removing drivers/net/sk_g16.h\n fatal: merge program failed\n Automatic merge failed; fix up by hand\n : siamese; git-update-cache --refresh\n drivers/net/r8169.c: needs update\n : siamese; echo $?\n 1\n : siamese; git diff -r 0e396ee43e445cb7c215a98da4e76d0ce354d9d7\n :100644 100644 ce449fe 0000000 M\tdrivers/net/r8169.c\n : siamese; exit\n\nIn the above example, 'resolve', 'multibase' and 'octopus' are\ntried in turn (actually, 'octopus' notices that it is given only\none and refuses to do anything without wasting time).\nSince all of these strategies fail to fully auto-merge the given\nheads, and 'multibase' gives the smallest number of conflicts,\nits result is left in the working tree for the user to resolve\nby hand. You resolve this and commit the same way as you\ncurrently do with 'git-resolve' that results in conflicts.\n\n\n[Footnote]\n\n*1* Fredrik, I have been wondering if we can just say that lack\nof '-u' flag implies '-i'. Is there a good reason that\n'git-read-tree -m O A B' without '-u' should care if working\ntree is up to date for the paths involved?\n"},{"id":"8237","messageId":"Pine.LNX.4.63.0509091151520.23242@iabervon.org","threadId":"1743","inReplyTo":"7v3boen0rb.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [RFH] Merge driver","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-09T16:05:33Z","receivedAt":"2005-09-09T16:05:33Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Fri, 9 Sep 2005, Junio C Hamano wrote:\n\n> I have several requests to people who are interested in merges\n> and read-tree changes.\n> \n> I am pretty much set to use the recent read-tree updates Daniel\n> has been working on. The only reason it has not hit the\n> \"master\" branch yet, except that it still has known leaks that\n> have not been plugged, is because read-tree is so fundamental to\n> everything we do, and I am trying to be extremely conservative\n> here. I've beaten it myself reasonably well and have not found\n> any regressions (except removal of --emu23 which I believe\n> nobody uses anyway), but I'd appreciate people to try it out and\n> see if it performs well for your dataset.\n> \n> If you are planning further surgery on read-tree code, please\n> base your changes on Daniel's rewrite to avoid your effort being\n> wasted. This request goes both to Chuck (active_cache\n> abstraction) and Fredrik (addition of 'ignore index and working\n> tree matching rules' [*1*]).\n> \n> A proposed merge driver 'git-merge' is in the proposed updates\n> branch. This is intended to be the top-level user interface to\n> the merge machinery which drives multiple merge strategy\n> scripts, and I am hoping that I can eventually (1) retire\n> 'git-resolve' and 'git-octopus' (they simply become merge\n> strategy scripts driven by 'git-merge') and (2) call 'git-merge'\n> from 'git-pull'. What I have in the proposed updates branch has\n> been fixed since my earlier message to the list and has a new\n> merge strategy script, in addition to 'resolve' and 'octopus',\n> called 'git-merge-multibase'. This uses Daniel's read-tree that\n> can use more than one merge bases. I request Daniel to give OK\n> to its name or suggest a better name for this script -- I would\n> even accept 'git-merge-barkalow' if you want ;-).\n\nI'd actually been thinking it would just go into the the \"resolve\" driver, \nwith that going back to before it chose among merge-base outputs and just \nsending the whole list to read-tree.\n\n> If you are planning to implement a new merge strategy, please\n> use the ones in the proposed updates branch as examples, and\n> complain and suggest improvements if you find the interface\n> between the strategy scripts and the driver lacking. This\n> request goes primarily to Fredrik. I'm interested in doing the\n> renaming merge that would have helped HPA's klibc-kbuild vs\n> klibc case myself but if somebody else is so inclined please go\n> wild.\n> \n> And finally, a request to everybody; please try out 'git-merge'\n> and see how you like it.\n> \n> `git-merge` [-n] [-s ]... ...\n> \n> -n::\n> \tDo not show diffstat at the end of the merge.\n> \n> -s ::\n> \tuse that merge strategy; can be given more than once to\n> \tspecify them in the order they should be tried. If\n> \tthere is no `-s` option, built-in list of strategies is\n> \tused instead.\n> \n> ::\n> \tour branch head commit.\n> \n> ::\n> \tother branch head merged into our branch. You need at\n> \tleast one . Specifying more than one \n> \tobviously means you are trying an Octopus.\n> \n> Here is a sample transcript from a test resolving one of the\n> 'more-than-one-merge-base' commits Fredrik found in the kernel\n> repository (\": siamese;\" is my $PS1; \" \" is my $PS2).\n> \n> : siamese; git reset --hard b8112df71cae7d6a86158caeb19d215f56c4f9ab\n> : siamese; git merge -n \\\n> 'reproduce 0e396ee43e445cb7c215a98da4e76d0ce354d9d7' \\\n> HEAD 2089a0d38bc9c2cdd084207ebf7082b18cf4bf58\n> Trying merge strategy resolve...\n> Trying to find the optimum merge base.\n> Trying simple merge.\n> Simple merge failed, trying Automatic merge.\n> Removing drivers/net/fmv18x.c\n> Auto-merging drivers/net/r8169.c.\n> merge: warning: conflicts during merge\n> ERROR: Merge conflict in drivers/net/r8169.c.\n> Removing drivers/net/sk_g16.c\n> Removing drivers/net/sk_g16.h\n> fatal: merge program failed\n> Rewinding the tree to pristine...\n> Trying merge strategy multibase...\n> Trying simple merge.\n> Simple merge failed, trying Automatic merge.\n> Removing drivers/net/fmv18x.c\n> Auto-merging drivers/net/r8169.c.\n> merge: warning: conflicts during merge\n> ERROR: Merge conflict in drivers/net/r8169.c.\n> Removing drivers/net/sk_g16.c\n> Removing drivers/net/sk_g16.h\n> fatal: merge program failed\n> Rewinding the tree to pristine...\n> Trying merge strategy octopus...\n> Rewinding the tree to pristine...\n> Using the multibase to prepare resolving by hand.\n> Trying simple merge.\n> Simple merge failed, trying Automatic merge.\n> Removing drivers/net/fmv18x.c\n> Auto-merging drivers/net/r8169.c.\n> merge: warning: conflicts during merge\n> ERROR: Merge conflict in drivers/net/r8169.c.\n> Removing drivers/net/sk_g16.c\n> Removing drivers/net/sk_g16.h\n> fatal: merge program failed\n> Automatic merge failed; fix up by hand\n> : siamese; git-update-cache --refresh\n> drivers/net/r8169.c: needs update\n> : siamese; echo $?\n> 1\n> : siamese; git diff -r 0e396ee43e445cb7c215a98da4e76d0ce354d9d7\n> :100644 100644 ce449fe 0000000 M\tdrivers/net/r8169.c\n> : siamese; exit\n> \n> In the above example, 'resolve', 'multibase' and 'octopus' are\n> tried in turn (actually, 'octopus' notices that it is given only\n> one and refuses to do anything without wasting time).\n> Since all of these strategies fail to fully auto-merge the given\n> heads, and 'multibase' gives the smallest number of conflicts,\n> its result is left in the working tree for the user to resolve\n> by hand. You resolve this and commit the same way as you\n> currently do with 'git-resolve' that results in conflicts.\n\nThis is no good: the current 'resolve' can generate wrong results and \nreport that it worked cleanly, while 'multibase' would report a conflict \nbecause it isn't ignoring a real problem. My primary goal in doing the \nmultibase version wasn't to produce more clean merges; it was to produce \nfewer clean-but-wrong merges.\n\n> [Footnote]\n> \n> *1* Fredrik, I have been wondering if we can just say that lack\n> of '-u' flag implies '-i'. Is there a good reason that\n> 'git-read-tree -m O A B' without '-u' should care if working\n> tree is up to date for the paths involved?\n\nIt tries to make sure that there is room to put stuff for resolving a \nconflict without messing with modified files in the directory.\n"},{"id":"8238","messageId":"7vy866jio4.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"Pine.LNX.4.63.0509091151520.23242@iabervon.org","subject":"Re: [RFH] Merge driver","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-09T16:43:39Z","receivedAt":"2005-09-09T16:43:39Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow writes:\n\n> I'd actually been thinking it would just go into the the \"resolve\" driver, \n> with that going back to before it chose among merge-base outputs and just \n> sending the whole list to read-tree.\n>\n> This is no good: the current 'resolve' can generate wrong results and \n> report that it worked cleanly, while 'multibase' would report a conflict \n> because it isn't ignoring a real problem. My primary goal in doing the \n> multibase version wasn't to produce more clean merges; it was to produce \n> fewer clean-but-wrong merges.\n\nTrue. Before 'git-merge' hits the \"master\" branch I should\nremove 'git-merge-resolve' from the strategies list (or rename\n'git-merge-multibase' to it). I have them separately only\nbecause I wanted to be able to see how differently they perform\nby saying:\n\n git merge -s resolve blah...\n git merge -s multibase blah...\n\n>> *1* Fredrik, I have been wondering if we can just say that lack\n>> of '-u' flag implies '-i'. Is there a good reason that\n>> 'git-read-tree -m O A B' without '-u' should care if working\n>> tree is up to date for the paths involved?\n>\n> It tries to make sure that there is room to put stuff for resolving a \n> conflict without messing with modified files in the directory.\n\nI agree it can be used that way, but nobody seems to use it for\nthat purpose as far as I can tell hence my earlier comment. But\nlet's leave the door open by having them as independent\noptions.\n"},{"id":"8241","messageId":"Pine.LNX.4.63.0509091320420.23242@iabervon.org","threadId":"1743","inReplyTo":"7vy866jio4.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] Merge driver","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-09T17:25:09Z","receivedAt":"2005-09-09T17:25:09Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Fri, 9 Sep 2005, Junio C Hamano wrote:\n\n> Daniel Barkalow writes:\n> \n> > It tries to make sure that there is room to put stuff for resolving a \n> > conflict without messing with modified files in the directory.\n> \n> I agree it can be used that way, but nobody seems to use it for\n> that purpose as far as I can tell hence my earlier comment. But\n> let's leave the door open by having them as independent\n> options.\n\nAh, okay. I hadn't realized that resolve used -u for that call to \nread-tree. You're entirely right.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8262","messageId":"7vzmqk2u1w.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"20050907165012.GA20392@c165.ib.student.liu.se","subject":"Unified merge driver pushed out to \"master\" branch","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-11T02:54:19Z","receivedAt":"2005-09-11T02:54:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I've pushed out the 'git merge' along with Daniel's read-tree\nupdates and your 'base on merge of bases' merge strategy driver\nin the \"master\" branch.\n\nThe last one is what I butchered your code without really\nauditing the changes I made, so I'd appreciate you to take a\nlook at it and supply any necessary updates and fixes. My\nchanges are meant to be only to adjust the calling convention to\nthat of 'git merge' -- that is, it gets merge bases and heads\nfrom the command line, and it is not supposed to commit and\nupdate HEAD itself, but is supposed to leave its best effort in\nthe working tree and the paths that cannot be automerged should\nbe left as that of HEAD version in the index file, so that the\nuser can run 'git diff' to see what is happening while resolving\nthings by hand. I do not think my change did the last part\ncorrectlyx. The change to introduce '-i' option to read-tree is\nalso present.\n\nI primarily used the commits found in the Linux 2.6 repository\nand its derivatives that have multiple potential merge bases for\nmy testing. Among them, the attempt to merge parents of this\ncommit triggered an assertion failure -- it may be my fault but\nI have not spent much time to diagnose it.\n\ncommit 6358924b06cd1aaa031b8ba0c33e5a15e795bef0\nMerge: 1da21e73bdc458f8131e6071072632b4c3b0430f 344a076110f4ecb16ea6d286b63be696604982ed\nAuthor: Tony Luck \nDate: Thu Sep 8 14:29:32 2005 -0700\n\n Pull release into test branch\n\n----------------------------------------------------------------\nHere is a summary of my test results.\n\n\"Expect\" names the commit being tested. The parents of each of\nthese commits have more than one merge-base, and the test is to\nstart from one parent of it, and merge the other parent into it\nusing the four merge programs:\n\n * traditional is 'git-resolve-script' from GIT 0.99.6 (it does\n not even use Daniel's read-tree so that I can catch\n regression in read-tree).\n\n * dbrt is 'git-merge -s resolve', i.e. Daniel's multi-base merge.\n\n * stupid is 'git-merge -s stupid', supposed to be the same\n as 'git-resolve' (but internally uses Daniel's read-tree with\n only one merge base).\n\n * fredrik is 'git-merge -s fredrik', the one I butchered.\n\n------------------------------------------------\nExpect 0c168775709faa74c1b87f1e61046e0c51ade7f3\nMethod 'traditional' failed to automerge.\nMethod 'dbrt' failed to automerge.\nMethod 'stupid' failed to automerge.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nThe fredrik is the only one that merged successfully, but its\nresult is different from the actual commit.\n\n:100644 100644 065b702df56353a00d5f460cf385f172decccf2b cd4222ff8b925f6b92414d58729d225fccc3f310 M\tinclude/net/ieee80211.h\n\n------------------------------------------------\nExpect 0c3e091838f02c537ccab3b6e8180091080f7df2 (case #16)\nMethod 'traditional' automerged\nMethod 'traditional' resolved cleanly.\nMethod 'dbrt' failed to automerge.\nMethod 'stupid' automerged\nMethod 'stupid' resolved cleanly.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nThe fredrik result is different from the actual commit.\n\n:100644 100644 a7bed60b69f9e8de9a49944e22d03fb388ae93c7 51a7b7b4dd0e7c5720683a40637cdb79a31ec4c4 M\tarch/ia64/hp/sim/boot/bootloader.c\n\n------------------------------------------------\nExpect 0e396ee43e445cb7c215a98da4e76d0ce354d9d7\nMethod 'traditional' failed to automerge.\nMethod 'dbrt' failed to automerge.\nMethod 'stupid' failed to automerge.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nThe fredrik is the only one that merged successfully, and its\nresult matches the actual commit.\n\n------------------------------------------------\nExpect 1960ff70a6c1db8e5f8fa9ec7020ef585f8ce706\nMethod 'traditional' automerged\nMethod 'traditional' resolved cleanly.\nMethod 'dbrt' automerged\nMethod 'dbrt' resolved cleanly.\nMethod 'stupid' automerged\nMethod 'stupid' resolved cleanly.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nAll results match the actual commit.\n\n------------------------------------------------\nExpect 19925d7e0af7de645d808fd973ef99049fce52f0\nMethod 'traditional' automerged\nMethod 'traditional' resolved cleanly.\nMethod 'dbrt' automerged\nMethod 'dbrt' resolved cleanly.\nMethod 'stupid' automerged\nMethod 'stupid' resolved cleanly.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nAll results match the actual commit.\n\n------------------------------------------------\nExpect 3190186362466658f01b2e354e639378ce07e1a9\nMethod 'traditional' automerged\nMethod 'traditional' resolved cleanly.\nMethod 'dbrt' automerged\nMethod 'dbrt' resolved cleanly.\nMethod 'stupid' automerged\nMethod 'stupid' resolved cleanly.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nAll results match the actual commit.\n\n------------------------------------------------\nExpect 467ca22d3371f132ee225a5591a1ed0cd518cb3d\nMethod 'traditional' automerged\nMethod 'traditional' resolved cleanly.\nMethod 'dbrt' automerged\nMethod 'dbrt' resolved cleanly.\nMethod 'stupid' automerged\nMethod 'stupid' resolved cleanly.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nAll results match the actual commit.\n\n------------------------------------------------\nExpect 539aeb871b52233b189ae976dfded20e14db645a\nMethod 'traditional' automerged\nMethod 'traditional' resolved cleanly.\nMethod 'dbrt' automerged\nMethod 'dbrt' resolved cleanly.\nMethod 'stupid' automerged\nMethod 'stupid' resolved cleanly.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nAll results match the actual commit.\n\n------------------------------------------------\nExpect 6358924b06cd1aaa031b8ba0c33e5a15e795bef0\nMethod 'traditional' automerged\nMethod 'traditional' resolved cleanly.\nMethod 'dbrt' automerged\nMethod 'dbrt' resolved cleanly.\nMethod 'stupid' automerged\nMethod 'stupid' resolved cleanly.\nMethod 'fredrik' failed to automerge.\n\nFredrik dies on asserttion failure.\n\n------------------------------------------------\nExpect 84ffa747520edd4556b136bdfc9df9eb1673ce12 (case #16)\nMethod 'traditional' failed to automerge.\nMethod 'dbrt' failed to automerge.\nMethod 'stupid' failed to automerge.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nThe fredrik result matches the actual commit.\n\n------------------------------------------------\nExpect a855f9a4d29f0ec338c337358844389171b0bae0\nMethod 'traditional' failed to automerge.\nMethod 'dbrt' automerged\nMethod 'dbrt' resolved cleanly.\nMethod 'stupid' failed to automerge.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nBoth fredrik and dbrt results match the actual commit.\n\n------------------------------------------------\nExpect cf70be167c085af820c0c2a606cab8c3ee819dc6\nMethod 'traditional' automerged\nMethod 'traditional' resolved cleanly.\nMethod 'dbrt' automerged\nMethod 'dbrt' resolved cleanly.\nMethod 'stupid' automerged\nMethod 'stupid' resolved cleanly.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nAll results match the actual commit.\n\n------------------------------------------------\nExpect da28c12089dfcfb8695b6b555cdb8e03dda2b690\nMethod 'traditional' automerged\nMethod 'traditional' resolved cleanly.\nMethod 'dbrt' automerged\nMethod 'dbrt' resolved cleanly.\nMethod 'stupid' automerged\nMethod 'stupid' resolved cleanly.\nMethod 'fredrik' automerged\nMethod 'fredrik' resolved cleanly.\n\nAll results match the actual commit.\n\n------------------------------------------------\n"},{"id":"8263","messageId":"7vr7bwxks3.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"7v3boen0rb.fsf_-_@assigned-by-dhcp.cox.net","subject":"[RFH] Merge driver","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-11T04:58:52Z","receivedAt":"2005-09-11T04:58:52Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Some people may be alarmed and feel concerned that I already\nhave Daniel's and Fredrik's merge in the \"master\" branch; I feel\nthis deserves some clarification.\n\nThe change Daniel made is a natural enhancement of an existing\nprogram. It spent unusually long time in the proposed update\nqueue exactly because read-tree was so fundamental, and I wanted\nto make sure there is no serious regression. Most importantly,\nthe original merge mechanism, git-resolve, is not dropped, and\n'git-pull' uses that, not 'git-merge', after fetching a remote\nhead. So for everyday use, nothing has changed.\n\nI did the 'git-merge' strategy backend mechanism because I\nwanted to play it safe. It makes it easy to give the set of\nconservative strategies as default for every day use, while\nallowing us to try more experimental strategies which can be\nused only by an explicit user request. Introduction of\nadditional merge strategies, such as the Fredrik merge or\nrename-detect merge which is yet to be written, is in a sense\nsimilar to adding new filesystems to the stable kernel tree --\nas long as they stay optional and do not touch the core deeply,\nthey tend to be safer changes than other kinds, and we can add\nthem more or less anytime in the stable series without impacting\nstability.\n\nI intend to eventually update git-pull to use git-merge, and I\nam hoping that I can do so before we hit 1.0, once we are sure\nthat 'git-merge -s stupid' behaves identically as 'git-resolve',\nand 'git-merge -s resolve' fares no worse than 'git-resolve'. I\npersonally feel I've done enough tests to ensure that already,\nbut help from the community is as always appreciated.\n"},{"id":"8325","messageId":"20050911210557.GC7486@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"7vzmqk2u1w.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: Unified merge driver pushed out to \"master\" branch","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-11T21:05:57Z","receivedAt":"2005-09-11T21:05:57Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Sat, Sep 10, 2005 at 07:54:19PM -0700, Junio C Hamano wrote:\n> I've pushed out the 'git merge' along with Daniel's read-tree\n> updates and your 'base on merge of bases' merge strategy driver\n> in the \"master\" branch.\n> \n> The last one is what I butchered your code without really\n> auditing the changes I made, so I'd appreciate you to take a\n> look at it and supply any necessary updates and fixes. My\n> changes are meant to be only to adjust the calling convention to\n> that of 'git merge' -- that is, it gets merge bases and heads\n> from the command line, and it is not supposed to commit and\n> update HEAD itself, but is supposed to leave its best effort in\n> the working tree and the paths that cannot be automerged should\n> be left as that of HEAD version in the index file, so that the\n> user can run 'git diff' to see what is happening while resolving\n> things by hand. I do not think my change did the last part\n> correctlyx. The change to introduce '-i' option to read-tree is\n> also present.\n\nYour changes seems to be fine.\n\nI am a bit confused about in what state the index should be in after a\nnon-clean merge.\n\nI interpreted <7vmzn2prck.fsf@assigned-by-dhcp.cox.net> as follows:\n\nThe index should preferably contain unmerged entries after a merge if\nthe merge was non-clean. If, for example, the file 'a' is modified in\nbranch A and 'a' is also modified in branch 'B' in such a way that\nmerge(1) cannot merge those changes, then when we have merged A with B\ngit-ls-files --unmerged should list 'a' in its output.\n\nHowever, according to my tests 'git merge -s resolve' doesn't do\nthis. (the old git-resolve-script didn't do this either) They both\nupdate the unmerged index entries to the entries that was in HEAD,\nwhich agrees with your description of how things are supposed to work\nabove.\n\nThe way the 'resolve' strategy do this seems to be more usable than\n\"leave unmerged entries in the cache\". In particular, 'git diff' gives\na usable output in this case.\n\nShould I change git-merge-fredrik.py to have the same behaviour as the\nresolve strategy?\n\n> I primarily used the commits found in the Linux 2.6 repository\n> and its derivatives that have multiple potential merge bases for\n> my testing. Among them, the attempt to merge parents of this\n> commit triggered an assertion failure -- it may be my fault but\n> I have not spent much time to diagnose it.\n> \n> commit 6358924b06cd1aaa031b8ba0c33e5a15e795bef0\n> Merge: 1da21e73bdc458f8131e6071072632b4c3b0430f 344a076110f4ecb16ea6d286b63be696604982ed\n> Author: Tony Luck \n> Date: Thu Sep 8 14:29:32 2005 -0700\n> \n> Pull release into test branch\n> \n\nIt was not your fault. I have a fix for it in my local tree, it will\nbe sent to the mailing list soon. The result match the actual commit\nwhen this patch has been applied.\n\n\n> ----------------------------------------------------------------\n> Here is a summary of my test results.\n> \n> \"Expect\" names the commit being tested. The parents of each of\n> these commits have more than one merge-base, and the test is to\n> start from one parent of it, and merge the other parent into it\n> using the four merge programs:\n> \n> * traditional is 'git-resolve-script' from GIT 0.99.6 (it does\n> not even use Daniel's read-tree so that I can catch\n> regression in read-tree).\n> \n> * dbrt is 'git-merge -s resolve', i.e. Daniel's multi-base merge.\n> \n> * stupid is 'git-merge -s stupid', supposed to be the same\n> as 'git-resolve' (but internally uses Daniel's read-tree with\n> only one merge base).\n> \n> * fredrik is 'git-merge -s fredrik', the one I butchered.\n> \n> ------------------------------------------------\n> Expect 0c168775709faa74c1b87f1e61046e0c51ade7f3\n> Method 'traditional' failed to automerge.\n> Method 'dbrt' failed to automerge.\n> Method 'stupid' failed to automerge.\n> Method 'fredrik' automerged\n> Method 'fredrik' resolved cleanly.\n> \n> The fredrik is the only one that merged successfully, but its\n> result is different from the actual commit.\n> \n> :100644 100644 065b702df56353a00d5f460cf385f172decccf2b cd4222ff8b925f6b92414d58729d225fccc3f310 M\tinclude/net/ieee80211.h\n> \n\nI believe my algorithm produces the correct result in this case. I\nthink the difference comes from manual edits to\ninclude/net/ieee80211.h after the merge but before the commit.\n\nThis commit was mentioned in\n<20050908200559.GA26088@c165.ib.student.liu.se>.\n\n\n> ------------------------------------------------\n> Expect 0c3e091838f02c537ccab3b6e8180091080f7df2 (case #16)\n> Method 'traditional' automerged\n> Method 'traditional' resolved cleanly.\n> Method 'dbrt' failed to automerge.\n> Method 'stupid' automerged\n> Method 'stupid' resolved cleanly.\n> Method 'fredrik' automerged\n> Method 'fredrik' resolved cleanly.\n> \n> The fredrik result is different from the actual commit.\n> \n> :100644 100644 a7bed60b69f9e8de9a49944e22d03fb388ae93c7 51a7b7b4dd0e7c5720683a40637cdb79a31ec4c4 M\tarch/ia64/hp/sim/boot/bootloader.c\n> \n\nThis is Tony Luck's test case, originally described in\n<200508232256.j7NMuR1q027892@agluck-lia64.sc.intel.com>.\n\nI reported the results for my algorithm on this case in\n<20050826184731.GA13629@c165.ib.student.liu.se>. I think that the\nresult produced by my algorithm is the result which Tony expected to\nget.\n\n\n- Fredrik\n"},{"id":"8351","messageId":"7vhdcroz9e.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"20050911210557.GC7486@c165.ib.student.liu.se","subject":"Re: Unified merge driver pushed out to \"master\" branch","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-12T01:23:09Z","receivedAt":"2005-09-12T01:23:09Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> I am a bit confused about in what state the index should be in after a\n> non-clean merge.\n\nYeah, I was confused when I wrote it. Sorry.\n\n> The way the 'resolve' strategy do this seems to be more usable than\n> \"leave unmerged entries in the cache\". In particular, 'git diff' gives\n> a usable output in this case.\n\nYou are certainly correct about what resolve does, and most\nlikely right what the most usable output is from an end user's\npoint of view. While merging, there _could_ be cases where we\nwould want to take a look at the current head of our head or the\ncurrent head of their head, but my reasoning that leaving those\nentries unmerged in the index file _might_ help that (which was\nthe reason behind that 'leave them unmerged' comment) was quite\nfaulty. We can say 'git-diff-cache HEAD' and 'git-diff-cache\nMERGE_HEAD' with and without --cached for that. I think the\ncurrent 'resolve' behaviour is the most useful one.\n\n> This is Tony Luck's test case, originally described in\n> <200508232256.j7NMuR1q027892@agluck-lia64.sc.intel.com>.\n>\n> I reported the results for my algorithm on this case in\n> <20050826184731.GA13629@c165.ib.student.liu.se>. I think that the\n> result produced by my algorithm is the result which Tony expected to\n> get.\n\nYeah, I agree. I might have sounded as if I was saying that the\nautomated merge must match the actual result otherwise it is\nbuggy, but that was not what I wanted to say -- rather we might\nhave found cases where the traditional 'git-resolve' did a wrong\nthing which slipped through unnoticed.\n"},{"id":"8424","messageId":"20050912210813.GA6644@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"7v3boen0rb.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [RFH] Merge driver","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-12T21:08:13Z","receivedAt":"2005-09-12T21:08:13Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Fri, Sep 09, 2005 at 12:44:40AM -0700, Junio C Hamano wrote:\n\n...\n\n> *1* Fredrik, I have been wondering if we can just say that lack\n> of '-u' flag implies '-i'. Is there a good reason that\n> 'git-read-tree -m O A B' without '-u' should care if working\n> tree is up to date for the paths involved?\n\nNo, I don't think so. But it would be nice if one could use '-i'\ntogether with '-u'.\n\nThe current git-merge-fredrik.py does not use '-i' together with '-u',\nbut I plan to change that. Currently we assume that the index is\nuptodate when we start the merge. If the two branches have more than\none common ancestor those ancestors are merged into a temporary tree,\nlets call it T, without touching the working directory.\n\nThe final steps of the merge are currently the following steps (lets\nsay we want to merge A with B):\n\ngit-read-tree A\ngit-update-cache --refresh\ngit-read-tree -u -m T A B\n\nWe need the second step because otherwise git-read-tree will complain\nthat the cache isn't uptodate. But we _know_ that the contents are\nuptodate, so the second step is unnecessary and just eats time. So,\ninstead of doing the above we should be able to do:\n\ngit-read-tree A\ngit-read-tree -u -i -m T A B\n\nI have a patch which implements this and it _seems_ to work fine. Is\nit reasonable to things this way or have I missed something?\n\n\n- Fredrik\n"},{"id":"8425","messageId":"7vmzmi9ebj.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"20050912210813.GA6644@c165.ib.student.liu.se","subject":"Re: [RFH] Merge driver","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-12T21:16:48Z","receivedAt":"2005-09-12T21:16:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> git-read-tree A\n> git-update-cache --refresh\n> git-read-tree -u -m T A B\n>\n> We need the second step because otherwise git-read-tree will complain\n> that the cache isn't uptodate. But we _know_ that the contents are\n> uptodate, so the second step is unnecessary and just eats time.\n\nIf we _know_ it should match, isn't there a way to tell the\nfirst \"git-read-tree A\" not to mess with the dirtiness, like,\nah, one-way merge?\n"},{"id":"8478","messageId":"20050913203252.GA1737@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"7vmzmi9ebj.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] Merge driver","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-13T20:33:06Z","receivedAt":"2005-09-13T20:33:06Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Mon, Sep 12, 2005 at 02:16:48PM -0700, Junio C Hamano wrote:\n> Fredrik Kuivinen writes:\n> \n> > git-read-tree A\n> > git-update-cache --refresh\n> > git-read-tree -u -m T A B\n> >\n> > We need the second step because otherwise git-read-tree will complain\n> > that the cache isn't uptodate. But we _know_ that the contents are\n> > uptodate, so the second step is unnecessary and just eats time.\n> \n> If we _know_ it should match, isn't there a way to tell the\n> first \"git-read-tree A\" not to mess with the dirtiness, like,\n> ah, one-way merge?\n> \n\nI don't think a one way merge will do what we want in this case.\n\nAt the start of the merge we know that the working directory is in\nsync with the index. But during the merge we will merge the common\nancestors, and the index file will be overwritten. When we are done\nwith merging the common ancestors we want to merge the heads that we\nwanted to merge from the begining (A and B) using T as the common\nancestor. When 'git-read-tree A' is executed we get a cache which has\nzeroed stat data, but SHAs and mode information which match the\nworking directory. If we do 'git-update-cache --refresh' the stat data\nwill be updated to match the working directory.\n\nUsing 'git-read-tree -m A' will not work because the stat data in the\ncache is zeroed before we run this command.\n\nI see two solutions, either allow passing '-i' together with '-u' to\ngit-read-tree or use a temporary index file when we are merging the\ncommon ancestors.\n\nThinking a bit more about it, maybe it's better to use a temporary\nindex file. If go this way we could, at least in principle, allow\nmerges which starts with a dirty working directory.\n\n- Fredrik\n"},{"id":"8479","messageId":"7vk6hk1ysa.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"20050913203252.GA1737@c165.ib.student.liu.se","subject":"Re: [RFH] Merge driver","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-13T20:46:29Z","receivedAt":"2005-09-13T20:46:29Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> Thinking a bit more about it, maybe it's better to use a temporary\n> index file. If go this way we could, at least in principle, allow\n> merges which starts with a dirty working directory.\n\nYeah, I like the idea of using temporary index for doing merges\nthat are not what the user wanted to do. The same idea is used\nin the 'stupid' thing that tries to find the least-conflicting\nmerge base.\n"},{"id":"8505","messageId":"7vpsrcqjj6.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"7vzmqk2u1w.fsf_-_@assigned-by-dhcp.cox.net","subject":"Another merge test case from the kernel tree.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-14T05:56:45Z","receivedAt":"2005-09-14T05:56:45Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"One more merge test case you would be interested. What's most\ninteresting about this commit is that it has three merge bases,\nnot two.\n\ncommit c820884e4f35a40f88b787c3891a23d629ef6bfd\nMerge: aa2dca4563b0629ecd9d9994dfdf39f29ff1b43f 357d596bd552ad157a906289ab13ea6ba7e66e3d\nAuthor: Tony Luck \nDate: Sun Sep 11 18:35:10 2005 -0700\n\n Auto-update from upstream\n\nAttempt to reproduce this commit is somewhat troubling. The\n'stupid' strategy and git-resolve resolves cleanly and Tony's\ncommit matches what 'git-resolve' does (obviously that is the\nalgorithm everybody uses).\n\nBut the 'resolve' strategy says this is case #16 (and resolves\nthis case differently but I think it is just by luck). This\nindicates that Tony _might_ have committed what he did not\nwanted to. The path involved is arch/mips/kernel/offset.c.\n\n [Tony, I think you've seen this one once in different\n commit. The terminology \"case #16\" means your merge has\n more than one merge base candidates:\n\n Ancestor#1 -- -- Your tree\n X\n Ancestor#2 -- -- Other tree\n\n and when a path in your tree matches Ancestor #i and the\n same path in the other tree matches Ancestor #j (i!=j).\n\n The default git merge algorithm picks a single ancestor that\n gives the least number of conflicting paths during the\n merge, and compares your tree and other tree against it and\n pick the one that changed since that ancestor if only one\n side changed that path. But in case #16, depending on which\n ancestor we pick, the result may come from your tree or\n other tree, and obviously we do a wrong thing with 50%\n probability.\n\n Thie _could_ indicate that you _might_ be losing a reverted\n you made in your line of development being overwritten by\n what the other tree did.]\n\nBTW, Fredrik, the 'recursive' merge dies with this:\n\nTrying merge strategy recursive...\nMerging 357d596bd552ad157a906289ab13ea6ba7e66e3d with aa2dca4563b0629ecd9d9994dfdf39f29ff1b43f\nMerging: \n357d596bd552ad157a906289ab13ea6ba7e66e3d Merge branch 'release' of master.kernel.org:/pub/scm/linux/kernel/git/aegl/linux-2.6 \naa2dca4563b0629ecd9d9994dfdf39f29ff1b43f Manual merge of kernel/sched.c and arch/ia64/kernel/mca_asm.S \nfound 3 common ancestor(s): \na1cddb88920b915eaba10712ecfd0fc698b00a22 [IA64-SGI] Add new vendor-specific SAL calls for: \n6cf07a8cc86a0b471466c7fe45892f7ef434015b [IA64] Fix nasty VMLPT problem... \n49a28cc8fd26f5317c47a9aeb2bdd1c33e21738e [IA64] MCA/INIT: remove obsolete unwind code \n Merging: \n a1cddb88920b915eaba10712ecfd0fc698b00a22 [IA64-SGI] Add new vendor-specific SAL calls for: \n 6cf07a8cc86a0b471466c7fe45892f7ef434015b [IA64] Fix nasty VMLPT problem... \n found 1 common ancestor(s): \n d8971fcb702e24d1e22c77fd1772f182ffee87e3 [INET]: compile errors when DEBUG is defined \nTraceback (most recent call last):\n File \"/home/junio/bin/Linux/git-merge-recursive\", line 429, in ?\n firstBranch, secondBranch, graph)\n File \"/home/junio/bin/Linux/git-merge-recursive\", line 54, in merge\n graph, callDepth+1)\n File \"/home/junio/bin/Linux/git-merge-recursive\", line 62, in merge\n runProgram(['git-read-tree', h1.tree()])\n File \"/home/junio/share/git-core/python/gitMergeCommon.py\", line 93, in runProgram\n raise ProgramError(progStr, out)\nProgramError: git-read-tree 1d20af805193ab9982a48cb4c828c0f6af034c6c: fatal: failed to unpack tree object 1d20af805193ab9982a48cb4c828c0f6af034c6c\n"},{"id":"8529","messageId":"Pine.LNX.4.63.0509141147230.23242@iabervon.org","threadId":"1743","inReplyTo":"7vpsrcqjj6.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: Another merge test case from the kernel tree.","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-14T16:11:00Z","receivedAt":"2005-09-14T16:11:00Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Tue, 13 Sep 2005, Junio C Hamano wrote:\n\n> One more merge test case you would be interested. What's most\n> interesting about this commit is that it has three merge bases,\n> not two.\n> \n> commit c820884e4f35a40f88b787c3891a23d629ef6bfd\n> Merge: aa2dca4563b0629ecd9d9994dfdf39f29ff1b43f 357d596bd552ad157a906289ab13ea6ba7e66e3d\n> Author: Tony Luck \n> Date: Sun Sep 11 18:35:10 2005 -0700\n> \n> Auto-update from upstream\n> \n> Attempt to reproduce this commit is somewhat troubling. The\n> 'stupid' strategy and git-resolve resolves cleanly and Tony's\n> commit matches what 'git-resolve' does (obviously that is the\n> algorithm everybody uses).\n> \n> But the 'resolve' strategy says this is case #16 (and resolves\n> this case differently but I think it is just by luck). This\n> indicates that Tony _might_ have committed what he did not\n> wanted to. The path involved is arch/mips/kernel/offset.c.\n\nIt shouldn't resolve it at all if it's case #16; I'll have to check on \nthat.\n\n> [Tony, I think you've seen this one once in different\n> commit. The terminology \"case #16\" means your merge has\n> more than one merge base candidates:\n> \n> Ancestor#1 -- -- Your tree\n> X\n> Ancestor#2 -- -- Other tree\n> \n> and when a path in your tree matches Ancestor #i and the\n> same path in the other tree matches Ancestor #j (i!=j).\n> \n> The default git merge algorithm picks a single ancestor that\n> gives the least number of conflicting paths during the\n> merge, and compares your tree and other tree against it and\n> pick the one that changed since that ancestor if only one\n> side changed that path. But in case #16, depending on which\n> ancestor we pick, the result may come from your tree or\n> other tree, and obviously we do a wrong thing with 50%\n> probability.\n> \n> Thie _could_ indicate that you _might_ be losing a reverted\n> you made in your line of development being overwritten by\n> what the other tree did.]\n\nMore precisely, case #16 only comes up when, in coming from the ancestors, \none side decided to match one ancestor, and the other side decided to \nmatch the other; it is rarely the case that this could occur due to the \ntwo merges making opposite decisions to entirely ignore the other \nancestor, and the only remaining case is that the merges each chose the \nsame ancestor, and one side reverted to the other. So it's pretty certain \nthat you've got a 50-50 chance of losing the correction.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8533","messageId":"7vpsrbobn5.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"Pine.LNX.4.63.0509141147230.23242@iabervon.org","subject":"Re: Another merge test case from the kernel tree.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-14T16:30:06Z","receivedAt":"2005-09-14T16:30:06Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow writes:\n\n> It shouldn't resolve it at all if it's case #16; I'll have to check on \n> that.\n\nSorry my mistake; it did not.\n"},{"id":"8538","messageId":"20050914174251.GA21639@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"7vpsrcqjj6.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: Another merge test case from the kernel tree.","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-14T17:42:51Z","receivedAt":"2005-09-14T17:42:51Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Tue, Sep 13, 2005 at 10:56:45PM -0700, Junio C Hamano wrote:\n...\n\n> BTW, Fredrik, the 'recursive' merge dies with this:\n> \n> Trying merge strategy recursive...\n> Merging 357d596bd552ad157a906289ab13ea6ba7e66e3d with aa2dca4563b0629ecd9d9994dfdf39f29ff1b43f\n> Merging: \n> 357d596bd552ad157a906289ab13ea6ba7e66e3d Merge branch 'release' of master.kernel.org:/pub/scm/linux/kernel/git/aegl/linux-2.6 \n> aa2dca4563b0629ecd9d9994dfdf39f29ff1b43f Manual merge of kernel/sched.c and arch/ia64/kernel/mca_asm.S \n> found 3 common ancestor(s): \n> a1cddb88920b915eaba10712ecfd0fc698b00a22 [IA64-SGI] Add new vendor-specific SAL calls for: \n> 6cf07a8cc86a0b471466c7fe45892f7ef434015b [IA64] Fix nasty VMLPT problem... \n> 49a28cc8fd26f5317c47a9aeb2bdd1c33e21738e [IA64] MCA/INIT: remove obsolete unwind code \n> Merging: \n> a1cddb88920b915eaba10712ecfd0fc698b00a22 [IA64-SGI] Add new vendor-specific SAL calls for: \n> 6cf07a8cc86a0b471466c7fe45892f7ef434015b [IA64] Fix nasty VMLPT problem... \n> found 1 common ancestor(s): \n> d8971fcb702e24d1e22c77fd1772f182ffee87e3 [INET]: compile errors when DEBUG is defined \n> Traceback (most recent call last):\n> File \"/home/junio/bin/Linux/git-merge-recursive\", line 429, in ?\n> firstBranch, secondBranch, graph)\n> File \"/home/junio/bin/Linux/git-merge-recursive\", line 54, in merge\n> graph, callDepth+1)\n> File \"/home/junio/bin/Linux/git-merge-recursive\", line 62, in merge\n> runProgram(['git-read-tree', h1.tree()])\n> File \"/home/junio/share/git-core/python/gitMergeCommon.py\", line 93, in runProgram\n> raise ProgramError(progStr, out)\n> ProgramError: git-read-tree 1d20af805193ab9982a48cb4c828c0f6af034c6c: fatal: failed to unpack tree object 1d20af805193ab9982a48cb4c828c0f6af034c6c\n> \n\nIt works for me. The 'recursive' strategy cleanly merges this and\nproduces a result identical to the actual commit.\n\nThe tree object 1d20af805193ab9982a48cb4c828c0f6af034c6c is the tree\nof the commit a1cddb88920b915eaba10712ecfd0fc698b00a22 which is one of\nthe common ancestors. Are you sure that you got the entire repository? \nIt took some time for me to figure out that 'git clone\nrsync://rsync.kernel.org/pub/scm/linux/kernel/git/aegl/linux-2.6.git\naegl.git' will _not_ give you a usable repository. You have to change\naegl.git/.git/objects/objects/info/alternates before it becomes\nusable.\n\n\n- Fredrik\n"},{"id":"8542","messageId":"7v7jdjleq6.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"20050914174251.GA21639@c165.ib.student.liu.se","subject":"Re: Another merge test case from the kernel tree.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-14T17:51:45Z","receivedAt":"2005-09-14T17:51:45Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> It works for me. The 'recursive' strategy cleanly merges this and\n> produces a result identical to the actual commit.\n>\n> The tree object 1d20af805193ab9982a48cb4c828c0f6af034c6c is the tree\n> of the commit a1cddb88920b915eaba10712ecfd0fc698b00a22 which is one of\n> the common ancestors. Are you sure that you got the entire repository? \n> It took some time for me to figure out that 'git clone\n> rsync://rsync.kernel.org/pub/scm/linux/kernel/git/aegl/linux-2.6.git\n> aegl.git' will _not_ give you a usable repository. You have to change\n> aegl.git/.git/objects/objects/info/alternates before it becomes\n> usable.\n\nAh, that figures.. I was looking at Tony's repository right\nnow.\n\nThanks.\n"},{"id":"8571","messageId":"7vvf13b1hi.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"7vpsrcqjj6.fsf_-_@assigned-by-dhcp.cox.net","subject":"Yet another set of merge test cases from the kernel tree.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-15T00:47:53Z","receivedAt":"2005-09-15T00:47:53Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I've tried to reproduce 400+ merges I picked up from various\nkernel trees that have more than one merge base.\n\nnumber of commits looked at : 83292\nnumber of merge commits : 11089\ncommits with more than one base : 426\n\nInterestingly enough, some of them have timestamps in 2002 or\n2003, and comparing what our merge strategies do with what\nactually got recorded is interesting. I hope comparing what was\nrecorded by the SCM used back then and what we would produce\ntoday given the same input does not violate any license\nagreements somebody might have ;-).\n\nI've taken a look at only handful of results, but I can already\nsee some patterns:\n\n - Overall we seem to do reasonably well -- IOW many merges are\n trivial even to 'stupid' strategy;\n\n - In some cases, all strategies do quite poorly. For example:\n\n 091cced38d83732ee3212806ef5ea07abbef01fe\n 44583d380d189095fa959ec8ba87f0cb6deb15f5\n\n - There are quite a few case #16 (45 out of 426). While\n 'stupid' strategy fails to merge many of them, there are\n plenty of cases that it trivially resolves to what the SCM\n used back then did. 'resolve' being too cautious _might_\n irritate some users in these cases, but personally I feel\n that being safer is better than letting ambiguities go\n unnoticed. It _might_ indicate that the SCM used back then\n made the same mistake as our 'stupid' strategy does today\n ;-). A couple of examples:\n\n 39284791a2ca8cb32b5597bf9ccf8e5c548e7aa7\n 662756c753b13231d437e4bc78032b5891c9d4ea\n\n - 'recursive' strategy seems to most often produce results that\n match what the SCM used back then did, but it still gets some\n cases different. E.g.\n\n 10f44c023ef22c8c125d5ef15bed560d46c66af9\n 2e7bdf93a8c4d7ecd54f1ceb19881faf0f6b14f3\n 46f58b7869ffd1f2009065ffa626db3b0498925a\n 5f4fbfe6d1986a99cb62f433346c92e57e7b9814\n 651a8cf62546f2425df09b1b4451fe317f84431d\n\nI have not really counted to make stats out of those 426 merge\nresults, and the above is just my first impressions after\nlooking at about two dozens or so.\n\n\n------------\ncommit 091cced38d83732ee3212806ef5ea07abbef01fe\nMerge: 80964be0914c821546d3673fcb552d5b87a44867 cb70bcabcfb745c7dee78792bd17fb5fd50b0950\nAuthor: Len Brown \nDate: Wed Nov 10 07:57:44 2004 -0500\n\n Merge intel.com:/home/lenb/src/26-stable-dev\n into intel.com:/home/lenb/src/26-latest-dev\n\ndifferences in paths: 4057\n\nTry resolving the old way.\nMethod 'traditional' automerged (1).\nMethod 'traditional' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 2\nDifference from the actual commit: 4\nDifference from the actual commit (cached): 2\n\nStrategy recursive.\nMethod 'recursive' automerged (0).\nMethod 'recursive' resolved cleanly.\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 1\n\nStrategy resolve.\nMethod 'resolve' automerged (1).\nMethod 'resolve' did not resolve cleanly.\n\tunmerged paths: 46\n\tconflict paths: 24\nDifference from the actual commit: 28\nDifference from the actual commit (cached): 27\n\nStrategy stupid.\nMethod 'stupid' automerged (1).\nMethod 'stupid' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 2\nDifference from the actual commit: 4\nDifference from the actual commit (cached): 2\n ------------------------------------------------ \ncommit 10f44c023ef22c8c125d5ef15bed560d46c66af9\nMerge: 5ad6b7ada85fa414a7e94c309ef9c73862c08f69 961c380cef0f1af06c254488d1a672324ec2b34a\nAuthor: Greg Kroah-Hartman \nDate: Tue Mar 2 03:27:45 2004 -0800\n\n Merge kroah.com:/home/linux/BK/bleed-2.6\n into kroah.com:/home/linux/BK/pci-2.6\n\ndifferences in paths: 273\n\nTry resolving the old way.\nMethod 'traditional' automerged (1).\nMethod 'traditional' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 1\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 0\n\nStrategy recursive.\nMethod 'recursive' automerged (0).\nMethod 'recursive' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n\nStrategy resolve.\nMethod 'resolve' automerged (1).\nMethod 'resolve' did not resolve cleanly.\n\tunmerged paths: 16\n\tconflict paths: 8\nDifference from the actual commit: 8\nDifference from the actual commit (cached): 8\n\nStrategy stupid.\nMethod 'stupid' automerged (1).\nMethod 'stupid' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 1\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 0\n ------------------------------------------------ \ncommit 2e7bdf93a8c4d7ecd54f1ceb19881faf0f6b14f3\nMerge: ad50ff186e3544ce316bc24e8b37e82b840b42e1 b1c237f8c2f529713c11839db9d49ed8cec1c607\nAuthor: Patrick Mochel \nDate: Mon Sep 8 21:22:38 2003 -0700\n\n Merge kernel.bkbits.net:linux-2.5-power\n into osdl.org:/home/mochel/src/kernel/linux-2.5-power\n\ndifferences in paths: 70\n\nTry resolving the old way.\nMethod 'traditional' automerged (1).\nMethod 'traditional' did not resolve cleanly.\n\tunmerged paths: 4\n\tconflict paths: 3\nDifference from the actual commit: 4\nDifference from the actual commit (cached): 3\n\nStrategy recursive.\nMethod 'recursive' automerged (0).\nMethod 'recursive' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n\nStrategy resolve.\nMethod 'resolve' automerged (1).\nMethod 'resolve' did not resolve cleanly.\n\tunmerged paths: 2\n\tconflict paths: 1\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 1\n\nStrategy stupid.\nMethod 'stupid' automerged (1).\nMethod 'stupid' did not resolve cleanly.\n\tunmerged paths: 4\n\tconflict paths: 3\nDifference from the actual commit: 4\nDifference from the actual commit (cached): 3\n ------------------------------------------------ \ncommit 39284791a2ca8cb32b5597bf9ccf8e5c548e7aa7\nMerge: f96645e41c946431b988e061fbc9dd4c7176e621 b335ff4d92816a6722fcf323c67b86af58eb5b9d\nAuthor: Keith M. Wesolowski \nDate: Sun Jul 11 10:20:23 2004 -0700\n\n Merge ssh://kernel.bkbits.net/sparc32-2.6\n into foobazco.org:/sources/2.5-sparc-todave\n\ndifferences in paths: 2316\n\nTry resolving the old way.\nMethod 'traditional' automerged (0).\nMethod 'traditional' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n\nStrategy recursive.\nMethod 'recursive' automerged (0).\nMethod 'recursive' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n\nStrategy resolve.\nMethod 'resolve' automerged (1).\nMethod 'resolve' did not resolve cleanly.\n\tunmerged paths: 4\n\tconflict paths: 2\nDifference from the actual commit: 4\nDifference from the actual commit (cached): 4\n\nStrategy stupid.\nMethod 'stupid' automerged (0).\nMethod 'stupid' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n ------------------------------------------------ \ncommit 44583d380d189095fa959ec8ba87f0cb6deb15f5\nMerge: 645dbacc0c65228151b7cbcb8a977c83328cef76 8bf1412a4bbfc9da0224e73203172f98f987b41a\nAuthor: Jeff Dike \nDate: Sun Dec 29 11:40:13 2002 -0500\n\n Merge uml.karaya.com:/home/jdike/linux/2.5/skas-2.5\n into uml.karaya.com:/home/jdike/linux/2.5/skas-2.5-linus\n\ndifferences in paths: 406\n\nTry resolving the old way.\nMethod 'traditional' automerged (0).\nMethod 'traditional' resolved cleanly.\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 1\n\nStrategy recursive.\nMethod 'recursive' automerged (1).\nMethod 'recursive' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 1\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 1\n\nStrategy resolve.\nMethod 'resolve' automerged (1).\nMethod 'resolve' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 1\nDifference from the actual commit: 2\nDifference from the actual commit (cached): 2\n\nStrategy stupid.\nMethod 'stupid' automerged (0).\nMethod 'stupid' resolved cleanly.\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 1\n ------------------------------------------------ \ncommit 46f58b7869ffd1f2009065ffa626db3b0498925a\nMerge: d98612ae0eac1053fe585c0b283a9d385ed80572 9dd6f379b26f49c5819e302156dabb2171721f78\nAuthor: James Simmons \nDate: Sat Nov 16 01:36:03 2002 -0800\n\n Merge\n\ndifferences in paths: 74\n\nTry resolving the old way.\nMethod 'traditional' automerged (1).\nMethod 'traditional' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 5\nDifference from the actual commit: 6\nDifference from the actual commit (cached): 5\n\nStrategy recursive.\nMethod 'recursive' automerged (1).\nMethod 'recursive' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 1\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 0\n\nStrategy resolve.\nMethod 'resolve' automerged (1).\nMethod 'resolve' did not resolve cleanly.\n\tunmerged paths: 4\n\tconflict paths: 3\nDifference from the actual commit: 3\nDifference from the actual commit (cached): 2\n\nStrategy stupid.\nMethod 'stupid' automerged (1).\nMethod 'stupid' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 5\nDifference from the actual commit: 6\nDifference from the actual commit (cached): 5\n ------------------------------------------------ \ncommit 5f4fbfe6d1986a99cb62f433346c92e57e7b9814\nMerge: 03fab1f6c2a2ac316da184d687276655b53d3290 e772cc0eea175593d25669e11433b9647f4051e5\nAuthor: James Simmons \nDate: Fri Feb 14 17:37:00 2003 -0800\n\n Merge bk://fbdev.bkbits.net/fbdev-2.5\n into kozmo.(none):/usr/src/fbdev-2.5\n\ndifferences in paths: 154\n\nTry resolving the old way.\nMethod 'traditional' automerged (1).\nMethod 'traditional' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 2\nDifference from the actual commit: 4\nDifference from the actual commit (cached): 2\n\nStrategy recursive.\nMethod 'recursive' automerged (0).\nMethod 'recursive' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n\nStrategy resolve.\nMethod 'resolve' automerged (1).\nMethod 'resolve' did not resolve cleanly.\n\tunmerged paths: 2\n\tconflict paths: 1\nDifference from the actual commit: 2\nDifference from the actual commit (cached): 2\n\nStrategy stupid.\nMethod 'stupid' automerged (1).\nMethod 'stupid' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 2\nDifference from the actual commit: 4\nDifference from the actual commit (cached): 2\n ------------------------------------------------ \ncommit 651a8cf62546f2425df09b1b4451fe317f84431d\nMerge: cbe9bae1575761d8dfa7dd4b07c94878ef95bab8 abb86e39e38666d8b0af1821cb7c036902bbf459\nAuthor: James Simmons \nDate: Thu Dec 5 17:48:25 2002 -0800\n\n Merge bk://fbdev.bkbits.net/fbdev-2.5\n into kozmo.(none):/usr/src/fbdev-2.5\n\ndifferences in paths: 312\n\nTry resolving the old way.\nMethod 'traditional' automerged (1).\nMethod 'traditional' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 1\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 1\n\nStrategy recursive.\nMethod 'recursive' automerged (0).\nMethod 'recursive' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n\nStrategy resolve.\nMethod 'resolve' automerged (0).\nMethod 'resolve' resolved cleanly.\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 1\n\nStrategy stupid.\nMethod 'stupid' automerged (1).\nMethod 'stupid' did not resolve cleanly.\n\tunmerged paths: 1\n\tconflict paths: 1\nDifference from the actual commit: 1\nDifference from the actual commit (cached): 1\n ------------------------------------------------ \ncommit 662756c753b13231d437e4bc78032b5891c9d4ea\nMerge: 1a89e511e152998311f49c60e55b21d48d1b8973 8d7c763253b85b5598e5975a5c88b896fefe2110\nAuthor: Tony Luck \nDate: Thu Mar 31 00:29:06 2005 -0800\n\n Merge intel.com:/data/home/aegl/BK/work/1\n into intel.com:/data/home/aegl/BK/linux-ia64-release-2.6.12\n\ndifferences in paths: 3303\n\nTry resolving the old way.\nMethod 'traditional' automerged (0).\nMethod 'traditional' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n\nStrategy recursive.\nMethod 'recursive' automerged (0).\nMethod 'recursive' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n\nStrategy resolve.\nMethod 'resolve' automerged (0).\nMethod 'resolve' resolved cleanly.\nDifference from the actual commit: 3\nDifference from the actual commit (cached): 3\n\nStrategy stupid.\nMethod 'stupid' automerged (0).\nMethod 'stupid' resolved cleanly.\nDifference from the actual commit: 0\nDifference from the actual commit (cached): 0\n ------------------------------------------------ \n#!/bin/sh\n\ncheck_result () {\n\t# method=$1, expect=$2\n\n\tresult_exit=$?\n\tcase \"$result_exit\" in\n\t0 | 1)\n\t\techo \"Method '$1' automerged ($result_exit).\"\n\t\tgit-update-cache --refresh >/dev/null\n\t\tunmerged=`git-ls-files --unmerged`\n\t\tconflict=`git-diff-files --name-only`\n\t\tcase \"$unmerged$conflict\" in\n\t\t'')\n\t\t\techo \"Method '$1' resolved cleanly.\"\n\t\t\t;;\n\t\t*)\n\t\t\techo \"Method '$1' did not resolve cleanly.\"\n\t\t\techo \"\tunmerged paths: \"`echo \"$unmerged\" | wc -l`\n\t\t\techo \"\tconflict paths: \"`echo \"$conflict\" | wc -l`\n\t\t\t;;\n\t\tesac\n\t\techo \"Difference from the actual commit: \"`\n\t\t\tgit-diff-cache --name-only \"$expect\" | wc -l`\n\t\techo \"Difference from the actual commit (cached): \"`\n\t\t\tgit-diff-cache --name-only --cached \"$expect\" | wc -l`\n\t\t;;\n\t*)\n\t\techo \"Method '$1' failed to automerge.\"\n\t\t;;\n\tesac\n}\n\nstrategies=$(git merge -s help 2>&1 | sed -e 's/available strategies are: //')\n\nrm -fr ./++merge-log\nmkdir -p ./++merge-log\n\nwhile read parents\ndo\n\tset x $parents; shift; head=\"$1\"; shift\n\tremote= expect= remotes_seen=\n\tfor x\n\tdo\n\t\tcase \"$x\" in\n\t\t'|')\n\t\t\tcase \"$remotes_seen\" in\n\t\t\tyes) break ;;\n\t\t\tesac\n\t\t\tremotes_seen=yes\n\t\t\tcontinue ;;\n\t\t?*)\n\t\t\tcase \"$remotes_seen\" in\n\t\t\tyes) expect=\"$x\"; break ;;\n\t\t\tesac\n\t\t\tremote=\"$remote$x \" ;;\n\t\tesac\n\tdone\n\n\techo \"Merge $remote into $head\"\n\techo\n\n (\n\t\n\tgit log --max-count=1 $expect\n\n\techo \"differences in paths: \"`\n\t\tgit-diff-tree -r --name-only $remote $head | wc -l`\n\n\techo\n\tgit reset --hard \"$head\"\n\techo \"Try resolving the old way.\"\n\t(\n\t\tPATH=$HOME/bin/Linux-0.99.6:/usr/bin:/bin\n\t\texport PATH\n\t\tgit-resolve-script $head $remote 'test merge with resolve'\n\t\texit $?\n\t) >./\"++merge-log/$expect.traditional\" 2>&1\n\tcheck_result traditional $expect\n\n\tfor s in $strategies\n\tdo\n\t case \"$s\" in octopus) continue ;; esac\n\t echo\n\t git reset --hard \"$head\"\n\t echo \"Strategy $s.\"\n\t git-merge -n -s $s \"test merge $s\" $head $remote \\\n\t\t>./\"++merge-log/$expect.$s\" 2>&1\n\t check_result $s $expect\n\tdone\n\n\techo ' ------------------------------------------------ '\n\n ) >./\"++merge-log/$expect\".log 2>&1\n\ndone <./++commit-check-out\n"},{"id":"8874","messageId":"20050919161312.GB1782@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"7vvf13b1hi.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: Yet another set of merge test cases from the kernel tree.","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-19T16:13:12Z","receivedAt":"2005-09-19T16:13:12Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Wed, Sep 14, 2005 at 05:47:53PM -0700, Junio C Hamano wrote:\n> I've tried to reproduce 400+ merges I picked up from various\n> kernel trees that have more than one merge base.\n> \n> number of commits looked at : 83292\n> number of merge commits : 11089\n> commits with more than one base : 426\n> \n> Interestingly enough, some of them have timestamps in 2002 or\n> 2003, and comparing what our merge strategies do with what\n> actually got recorded is interesting. I hope comparing what was\n> recorded by the SCM used back then and what we would produce\n> today given the same input does not violate any license\n> agreements somebody might have ;-).\n> \n> I've taken a look at only handful of results, but I can already\n> see some patterns:\n> \n> - Overall we seem to do reasonably well -- IOW many merges are\n> trivial even to 'stupid' strategy;\n> \n> - In some cases, all strategies do quite poorly. For example:\n> \n> 091cced38d83732ee3212806ef5ea07abbef01fe\n> 44583d380d189095fa959ec8ba87f0cb6deb15f5\n\n091c... seems to be a bit complicated. I have tried to understand what\nthe correct result should be, but I haven't managed to do that yet.\n\n4458... is kind of interesting as it has no less than six common\nancestors.\n\n\n> \n> - There are quite a few case #16 (45 out of 426). While\n> 'stupid' strategy fails to merge many of them, there are\n> plenty of cases that it trivially resolves to what the SCM\n> used back then did. 'resolve' being too cautious _might_\n> irritate some users in these cases, but personally I feel\n> that being safer is better than letting ambiguities go\n> unnoticed. It _might_ indicate that the SCM used back then\n> made the same mistake as our 'stupid' strategy does today\n> ;-). A couple of examples:\n> \n> 39284791a2ca8cb32b5597bf9ccf8e5c548e7aa7\n> 662756c753b13231d437e4bc78032b5891c9d4ea\n> \n> - 'recursive' strategy seems to most often produce results that\n> match what the SCM used back then did, but it still gets some\n> cases different. E.g.\n> \n> 10f44c023ef22c8c125d5ef15bed560d46c66af9\n> 2e7bdf93a8c4d7ecd54f1ceb19881faf0f6b14f3\n> 46f58b7869ffd1f2009065ffa626db3b0498925a\n> 5f4fbfe6d1986a99cb62f433346c92e57e7b9814\n> 651a8cf62546f2425df09b1b4451fe317f84431d\n>\n\nThe reason we get the wrong result for those is that they all involve\nrenames. I have an experimental patch at the end of this mail which\nmakes git-merge-recursive.py handle some rename cases. The support for\nrenames is currently interleaved with other unrelated changes and\nthis patch should not yet be considered for inclusion. With the rename\npatch we get clean merges that matches the actual commit for all of\nthose except for 46f5.... git-merge-recursive.py do not merge\n46f5... cleanly with the rename patch applied.\n\nPeter's merge, reported in <4318E754.9000703@zytor.com>, is merged\ncleanly if this patch is applied. (and I _think_ the result is\ncorrect)\n\n- Fredrik\n\n\n---\n\n git-merge-recursive.py | 466 +++++++++++++++++++++++++++++++++++--------------\n 1 files changed, 334 insertions(+), 132 deletions(-)\n\ndiff --git a/git-merge-recursive.py b/git-merge-recursive.py\n--- a/git-merge-recursive.py\n+++ b/git-merge-recursive.py\n@@ -7,9 +7,6 @@ from sets import Set\n sys.path.append('@@GIT_PYTHON_PATH@@')\n from gitMergeCommon import *\n \n-# The actual merge code\n-# ---------------------\n-\n originalIndexFile = os.environ.get('GIT_INDEX_FILE',\n os.environ.get('GIT_DIR', '.git') + '/index')\n temporaryIndexFile = os.environ.get('GIT_DIR', '.git') + \\\n@@ -26,6 +23,13 @@ def setupIndex(temporary):\n newIndex = originalIndexFile\n os.environ['GIT_INDEX_FILE'] = newIndex\n \n+def fmtP(path):\n+ '''Format path for printing'''\n+ return '\"' + path + '\"'\n+\n+# The entry point to the merge code\n+# ---------------------------------\n+\n def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):\n '''Merge the commits h1 and h2, return the resulting virtual\n commit object and a flag indicating the cleaness of the merge.'''\n@@ -74,7 +78,7 @@ def merge(h1, h2, branch1Name, branch2Na\n \n return [res, clean]\n \n-getFilesRE = re.compile(r'^([0-7]+) (\\S+) ([0-9a-f]{40})\\t(.*)$', re.S)\n+getFilesRE = re.compile('([0-9]+) ([a-z0-9]+) ([0-9a-f]{40})\\t(.*)')\n def getFilesAndDirs(tree):\n files = Set()\n dirs = Set()\n@@ -89,6 +93,149 @@ def getFilesAndDirs(tree):\n \n return [files, dirs]\n \n+def mergeTrees(head, merge, common, branch1Name, branch2Name,\n+ cleanCache):\n+ '''Merge the trees 'head' and 'merge' with the common ancestor\n+ 'common'. The name of the head branch is 'branch1Name' and the name of\n+ the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)\n+ where tree is the resulting tree and cleanMerge is True iff the\n+ merge was clean.'''\n+ \n+ assert(isSha(head) and isSha(merge) and isSha(common))\n+\n+ if common == merge:\n+ print 'Already uptodate!'\n+ return [head, True]\n+\n+ if cleanCache:\n+ updateArg = '-i'\n+ else:\n+ updateArg = '-u'\n+\n+ runProgram(['git-read-tree', updateArg, '-m', common, head, merge])\n+ cleanMerge = True\n+\n+ [tree, code] = runProgram('git-write-tree', returnCode=True)\n+ tree = tree.rstrip()\n+ if code != 0:\n+ [files, dirs] = getFilesAndDirs(head)\n+ [filesM, dirsM] = getFilesAndDirs(merge)\n+ files.union_update(filesM)\n+ dirs.union_update(dirsM)\n+ \n+ renamesHead = getRenames(common, head)\n+ renamesMerge = getRenames(common, merge)\n+\n+ entries = unmergedCacheEntries()\n+ cleanMerge = processRenames(entries, renamesHead, renamesMerge,\n+ branch1Name, branch2Name, cleanCache)\n+ for entry in entries.itervalues():\n+ if entry.processed:\n+ continue\n+ if not processEntry(entry, branch1Name, branch2Name,\n+ files, dirs, cleanCache):\n+ cleanMerge = False\n+ \n+ if cleanMerge or cleanCache:\n+ tree = runProgram('git-write-tree').rstrip()\n+ else:\n+ tree = None\n+ else:\n+ cleanMerge = True\n+\n+ return [tree, cleanMerge]\n+\n+# Low level file merging, update and removal\n+# ------------------------------------------\n+\n+MERGE_NOCHANGES = 0\n+MERGE_SIMPLE = 1\n+MERGE_3WAY = 2\n+def mergeFile(path, oSha, oMode, aSha, aMode, bSha, bMode,\n+ branch1Name, branch2Name):\n+\n+ merge = MERGE_NOCHANGES\n+ clean = True\n+\n+ if aSha != oSha or bSha != oSha:\n+ merge = MERGE_SIMPLE\n+\n+ if aSha == oSha:\n+ sha = bSha\n+ elif bSha == oSha:\n+ sha = aSha\n+ else:\n+ merge = MERGE_3WAY\n+ orig = runProgram(['git-unpack-file', oSha]).rstrip()\n+ src1 = runProgram(['git-unpack-file', aSha]).rstrip()\n+ src2 = runProgram(['git-unpack-file', bSha]).rstrip()\n+ [out, code] = runProgram(['merge',\n+ '-L', branch1Name + '/' + path,\n+ '-L', 'orig/' + path,\n+ '-L', branch2Name + '/' + path,\n+ src1, orig, src2], returnCode=True)\n+\n+ sha = runProgram(['git-hash-object', '-t', 'blob', '-w',\n+ src1]).rstrip()\n+\n+ os.unlink(orig)\n+ os.unlink(src1)\n+ os.unlink(src2)\n+\n+ clean = (code == 0)\n+\n+ if aMode == oMode:\n+ mode = bMode\n+ else:\n+ mode = aMode\n+\n+ return [sha, mode, clean, merge]\n+\n+def updateFile(clean, sha, mode, path, cleanCache, onlyWd=False):\n+ updateCache = not onlyWd and (cleanCache or (not cleanCache and clean))\n+ updateWd = onlyWd or (not cleanCache and clean)\n+\n+ if updateWd:\n+ prog = ['git-cat-file', 'blob', sha]\n+ if stat.S_ISREG(mode):\n+ try:\n+ os.unlink(path)\n+ except OSError:\n+ pass\n+ if mode & 0100:\n+ mode = 0777\n+ else:\n+ mode = 0666\n+ fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)\n+ proc = subprocess.Popen(prog, stdout=fd)\n+ proc.wait()\n+ os.close(fd)\n+ elif stat.S_ISLNK(mode):\n+ linkTarget = runProgram(prog)\n+ os.symlink(linkTarget, path)\n+ else:\n+ assert(False)\n+\n+ if updateWd and updateCache:\n+ runProgram(['git-update-index', '--add', '--', path])\n+ elif updateCache:\n+ runProgram(['git-update-index', '--add', '--cacheinfo',\n+ '0%o' % mode, sha, path])\n+\n+def removeFile(clean, path, cleanCache):\n+ if cleanCache or (not cleanCache and clean):\n+ runProgram(['git-update-index', '--force-remove', '--', path])\n+\n+ if not cleanCache and clean:\n+ try:\n+ os.unlink(path)\n+ except OSError, e:\n+ if e.errno != errno.ENOENT and e.errno != errno.EISDIR:\n+ raise\n+\n+# Cache entry management\n+# ----------------------\n+\n class CacheEntry:\n def __init__(self, path):\n class Stage:\n@@ -98,8 +245,15 @@ class CacheEntry:\n \n self.stages = [Stage(), Stage(), Stage()]\n self.path = path\n+ self.processed = False\n \n-unmergedRE = re.compile(r'^([0-7]+) ([0-9a-f]{40}) ([1-3])\\t(.*)$', re.S)\n+def getCacheEntry(entries, path):\n+ for e in entries.itervalues():\n+ if e.path == path:\n+ return e\n+ return None\n+\n+unmergedRE = re.compile('^([0-9]+) ([0-9a-f]{40}) ([1-3])\\t(.*)$')\n def unmergedCacheEntries():\n '''Create a dictionary mapping file names to CacheEntry\n objects. The dictionary contains one entry for every path with a\n@@ -130,52 +284,160 @@ def unmergedCacheEntries():\n 'git-ls-files:', l)\n return res\n \n-def mergeTrees(head, merge, common, branch1Name, branch2Name,\n- cleanCache):\n- '''Merge the trees 'head' and 'merge' with the common ancestor\n- 'common'. The name of the head branch is 'branch1Name' and the name of\n- the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)\n- where tree is the resulting tree and cleanMerge is True iff the\n- merge was clean.'''\n- \n- assert(isSha(head) and isSha(merge) and isSha(common))\n+# Rename detection and handling\n+# -----------------------------\n \n- if common == merge:\n- print 'Already uptodate!'\n- return [head, True]\n+class RenameEntry:\n+ def __init__(self, src, srcSha, srcMode, dst, dstSha, dstMode, score):\n+ self.srcName = src\n+ self.srcSha = srcSha\n+ self.srcMode = srcMode\n+ self.dstName = dst\n+ self.dstSha = dstSha\n+ self.dstMode = dstMode\n+ self.score = score\n+\n+class RenameInfo:\n+ def __init__(self):\n+ self.entriesSrc = {}\n+ self.entriesDst = {}\n+\n+ def add(self, entry):\n+ self.entriesSrc[entry.srcName] = entry\n+ self.entriesDst[entry.dstName] = entry\n+\n+ def getSrc(self, path):\n+ return self.entriesSrc.get(path)\n+\n+ def getDst(self, path):\n+ return self.entriesDst.get(path)\n+\n+ def __iter__(self):\n+ return self.entriesSrc.itervalues()\n+\n+parseDiffRenamesRE = re.compile(':([0-7]+) ([0-7]+) ([0-9a-f]{40}) ([0-9a-f]{40}) R([0-9]*)')\n+def getRenames(treeOrig, tree):\n+ inp = runProgram(['git-diff-tree', '-M', '--diff-filter=R', '-r', '-z', treeOrig, tree])\n \n- if cleanCache:\n- updateArg = '-i'\n- else:\n- updateArg = '-u'\n+ ret = RenameInfo()\n+ try:\n+ recs = inp.split(\"\\0\")\n+ recs.pop() # remove last entry (which is '')\n+ it = recs.__iter__()\n+ while True:\n+ rec = it.next()\n+ m = parseDiffRenamesRE.match(rec)\n+ \n+ if not m:\n+ die('Unexpected output from git-diff-tree!:', rec)\n+\n+ srcMode = int(m.group(1), 8)\n+ dstMode = int(m.group(2), 8)\n+ srcSha = m.group(3)\n+ dstSha = m.group(4)\n+ score = m.group(5)\n+ src = it.next()\n+ dst = it.next()\n+ ret.add(RenameEntry(src, srcSha, srcMode, dst, dstSha, dstMode, score))\n+ except StopIteration:\n+ pass\n+ return ret\n \n- runProgram(['git-read-tree', updateArg, '-m', common, head, merge])\n- cleanMerge = True\n+def processRenames(entries, renamesA, renamesB, branchNameA, branchNameB, cleanCache):\n+ srcNames = Set()\n+ for x in renamesA:\n+ srcNames.add(x.srcName)\n+ for x in renamesB:\n+ srcNames.add(x.srcName)\n \n- [tree, code] = runProgram('git-write-tree', returnCode=True)\n- tree = tree.rstrip()\n- if code != 0:\n- [files, dirs] = getFilesAndDirs(head)\n- [filesM, dirsM] = getFilesAndDirs(merge)\n- files.union_update(filesM)\n- dirs.union_update(dirsM)\n+ cleanMerge = True\n+ for path in srcNames:\n+ if renamesA.getSrc(path):\n+ renames1 = renamesA\n+ renames2 = renamesB\n+ branchName1 = branchNameA\n+ branchName2 = branchNameB\n+ else:\n+ renames1 = renamesB\n+ renames2 = renamesA\n+ branchName1 = branchNameB\n+ branchName2 = branchNameA\n \n- cleanMerge = True\n- entries = unmergedCacheEntries()\n- for name in entries:\n- if not processEntry(entries[name], branch1Name, branch2Name,\n- files, dirs, cleanCache):\n+ ren1 = renames1.getSrc(path)\n+ ren2 = renames2.getSrc(path)\n+\n+ e = getCacheEntry(entries, ren1.dstName)\n+ if e:\n+ e.processed = True\n+ e = getCacheEntry(entries, ren1.srcName)\n+ if e:\n+ e.processed = True\n+ removeFile(True, ren1.srcName, cleanCache)\n+ if ren2:\n+ assert(ren1.srcName == ren2.srcName)\n+ e = getCacheEntry(entries, ren2.dstName)\n+ if e:\n+ e.processed = True\n+ if ren1.dstName != ren2.dstName:\n+ print 'CONFLICT (ren/ren):', fmtP(path), 'renamed to', \\\n+ fmtP(ren1.dstName), 'in branch', branchName1, 'and to', fmtP(ren2.dstName), \\\n+ 'in', branchName2\n cleanMerge = False\n- \n- if cleanMerge or cleanCache:\n- tree = runProgram('git-write-tree').rstrip()\n+ updateFile(False, ren1.dstSha, ren1.dstMode, ren1.dstName, cleanCache)\n+ updateFile(False, ren2.dstSha, ren2.dstMode, ren2.dstName, cleanCache)\n+ else:\n+ print fmtP(path), 'renamed to', fmtP(ren1.dstName), 'in both branches'\n+ [resSha, resMode, clean, merge] = \\\n+ mergeFile(ren1.srcName,\n+ ren1.srcSha, ren1.srcMode,\n+ ren1.dstSha, ren1.dstMode,\n+ ren2.dstSha, ren2.dstMode,\n+ branchName1, branchName2)\n+\n+ if merge:\n+ print 'Auto-merging', fmtP(ren1.dstName)\n+\n+ if not clean:\n+ print 'CONFLICT (mod/mod): merge conflict in', fmtP(ren1.dstName)\n+ updateFile(clean, resSha, resMode, ren1.dstName, cleanCache)\n+ \n+ # Renamed in 1, maybe changed in 2\n else:\n- tree = None\n- else:\n- cleanMerge = True\n+ # FIXME ar det verkligen sakert att ren1.srcName finns i cachen som unmerged?\n+ e = getCacheEntry(entries, ren1.srcName)\n+ if renamesA == renames1:\n+ sha = e.stages[2].sha1\n+ mode = e.stages[2].mode\n+ else:\n+ sha = e.stages[1].sha1\n+ mode = e.stages[1].mode\n \n- return [tree, cleanMerge]\n+ [resSha, resMode, clean, merge] = \\\n+ mergeFile(ren1.srcName,\n+ ren1.srcSha, ren1.srcMode,\n+ ren1.dstSha, ren1.dstMode,\n+ sha, mode, branchName1, branchName2)\n+\n+ if merge:\n+ print fmtP(ren1.srcName), 'renamed to', fmtP(ren1.dstName), 'in', \\\n+ branchName1, 'and modified in', branchName2 + ', auto-merging'\n+\n+ if not clean:\n+ print 'CONFLICT (ren/mod):', fmtP(ren1.srcName), 'renamed to ', \\\n+ fmtP(ren1.dstName), 'in branch', branchName1, 'and modified in', \\\n+ 'branch', branchName2, 'merge conflict in', fmtP(ren1.dstName)\n+ cleanMerge = False\n+ else:\n+ print fmtP(ren1.srcName), 'renamed to', fmtP(ren1.dstName), 'in', \\\n+ branchName1\n \n+ e.processed = True\n+ updateFile(clean, resSha, resMode, ren1.dstName, cleanCache)\n+ return cleanMerge\n+\n+# Per entry merge function\n+# ------------------------\n+ \n def processEntry(entry, branch1Name, branch2Name, files, dirs, cleanCache):\n '''Merge one cache entry. 'files' is a Set with the files in both of\n the heads that we are going to merge. 'dirs' contains the\n@@ -192,48 +454,6 @@ def processEntry(entry, branch1Name, bra\n \n # If cleanCache == False then the cache shouldn't be updated if clean == False\n \n- def updateFile(clean, sha, mode, path, onlyWd=False):\n- updateCache = not onlyWd and (cleanCache or (not cleanCache and clean))\n- updateWd = onlyWd or (not cleanCache and clean)\n-\n- if updateWd:\n- prog = ['git-cat-file', 'blob', sha]\n- if stat.S_ISREG(mode):\n- try:\n- os.unlink(path)\n- except OSError:\n- pass\n- if mode & 0100:\n- mode = 0777\n- else:\n- mode = 0666\n- fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)\n- proc = subprocess.Popen(prog, stdout=fd)\n- proc.wait()\n- os.close(fd)\n- elif stat.S_ISLNK(mode):\n- linkTarget = runProgram(prog)\n- os.symlink(linkTarget, path)\n- else:\n- assert(False)\n-\n- if updateWd and updateCache:\n- runProgram(['git-update-index', '--add', '--', path])\n- elif updateCache:\n- runProgram(['git-update-index', '--add', '--cacheinfo',\n- '0%o' % mode, sha, path])\n-\n- def removeFile(clean, path):\n- if cleanCache or (not cleanCache and clean):\n- runProgram(['git-update-index', '--force-remove', '--', path])\n-\n- if not cleanCache and clean:\n- try:\n- os.unlink(path)\n- except OSError, e:\n- if e.errno != errno.ENOENT and e.errno != errno.EISDIR:\n- raise\n-\n def uniquePath(path, branch):\n newPath = path + '_' + branch\n suffix = 0\n@@ -273,26 +493,26 @@ def processEntry(entry, branch1Name, bra\n # Deleted in both or deleted in one and unchanged in the other\n if aSha:\n print 'Removing ' + path\n- removeFile(True, path)\n+ removeFile(True, path, cleanCache)\n else:\n # Deleted in one and changed in the other\n cleanMerge = False\n if not aSha:\n- print 'CONFLICT (del/mod): \"' + path + '\" deleted in', \\\n+ print 'CONFLICT (del/mod):', fmtP(path), ' deleted in', \\\n branch1Name, 'and modified in', branch2Name, \\\n- '. Version', branch2Name, ' of \"' + path + \\\n- '\" left in tree'\n+ '. Version', branch2Name, 'of', fmtP(path), \\\n+ 'left in tree'\n mode = bMode\n sha = bSha\n else:\n- print 'CONFLICT (mod/del): \"' + path + '\" deleted in', \\\n+ print 'CONFLICT (mod/del):', fmtP(path), 'deleted in', \\\n branch2Name, 'and modified in', branch1Name + \\\n- '. Version', branch1Name, 'of \"' + path + \\\n- '\" left in tree'\n+ '. Version', branch1Name, 'of', path, \\\n+ 'left in tree'\n mode = aMode\n sha = aSha\n \n- updateFile(False, sha, mode, path)\n+ updateFile(False, sha, mode, path, cleanCache)\n \n elif (not oSha and aSha and not bSha) or \\\n (not oSha and not aSha and bSha):\n@@ -316,15 +536,15 @@ def processEntry(entry, branch1Name, bra\n cleanMerge = False\n newPath = uniquePath(path, addBranch)\n print 'CONFLICT (' + conf + \\\n- '): There is a directory with name \"' + path + '\" in', \\\n- otherBranch + '. Adding \"' + path + '\" as \"' + newPath + '\"'\n+ '): There is a directory with name', path, 'in', \\\n+ otherBranch + '. Adding', fmtP(path), 'as', fmtP(newPath)\n \n- removeFile(False, path)\n+ removeFile(False, path, cleanCache)\n path = newPath\n else:\n- print 'Adding \"' + path + '\"'\n+ print 'Adding', fmtP(path)\n \n- updateFile(True, sha, mode, path)\n+ updateFile(True, sha, mode, path, cleanCache)\n \n elif not oSha and aSha and bSha:\n #\n@@ -333,13 +553,13 @@ def processEntry(entry, branch1Name, bra\n if aSha == bSha:\n if aMode != bMode:\n cleanMerge = False\n- print 'CONFLICT: File \"' + path + \\\n- '\" added identically in both branches,', \\\n+ print 'CONFLICT: File', fmtP(path), \\\n+ 'added identically in both branches,', \\\n 'but permissions conflict', '0%o' % aMode, '->', \\\n '0%o' % bMode\n print 'CONFLICT: adding with permission:', '0%o' % aMode\n \n- updateFile(False, aSha, aMode, path)\n+ updateFile(False, aSha, aMode, path, cleanCache)\n else:\n # This case is handled by git-read-tree\n assert(False)\n@@ -347,49 +567,31 @@ def processEntry(entry, branch1Name, bra\n cleanMerge = False\n newPath1 = uniquePath(path, branch1Name)\n newPath2 = uniquePath(path, branch2Name)\n- print 'CONFLICT (add/add): File \"' + path + \\\n- '\" added non-identically in both branches.'\n- removeFile(False, path)\n- updateFile(False, aSha, aMode, newPath1)\n- updateFile(False, bSha, bMode, newPath2)\n+ print 'CONFLICT (add/add): File', fmtP(path), \\\n+ 'added non-identically in both branches.'\n+ removeFile(False, path, cleanCache)\n+ updateFile(False, aSha, aMode, newPath1, cleanCache)\n+ updateFile(False, bSha, bMode, newPath2, cleanCache)\n \n elif oSha and aSha and bSha:\n #\n # case D: Modified in both, but differently.\n #\n print 'Auto-merging', path \n- orig = runProgram(['git-unpack-file', oSha]).rstrip()\n- src1 = runProgram(['git-unpack-file', aSha]).rstrip()\n- src2 = runProgram(['git-unpack-file', bSha]).rstrip()\n- [out, ret] = runProgram(['merge',\n- '-L', branch1Name + '/' + path,\n- '-L', 'orig/' + path,\n- '-L', branch2Name + '/' + path,\n- src1, orig, src2], returnCode=True)\n-\n- if aMode == oMode:\n- mode = bMode\n+ [sha, mode, clean, merge] = \\\n+ mergeFile(path, oSha, oMode, aSha, aMode, bSha, bMode,\n+ branch1Name, branch2Name)\n+ if clean:\n+ updateFile(True, sha, mode, path, cleanCache)\n else:\n- mode = aMode\n-\n- sha = runProgram(['git-hash-object', '-t', 'blob', '-w',\n- src1]).rstrip()\n-\n- if ret != 0:\n cleanMerge = False\n- print 'CONFLICT (content): Merge conflict in \"' + path + '\".'\n+ print 'CONFLICT (content): Merge conflict in', fmtP(path)\n \n if cleanCache:\n- updateFile(False, sha, mode, path)\n+ updateFile(False, sha, mode, path, cleanCache)\n else:\n- updateFile(True, aSha, aMode, path)\n- updateFile(False, sha, mode, path, True)\n- else:\n- updateFile(True, sha, mode, path)\n-\n- os.unlink(orig)\n- os.unlink(src1)\n- os.unlink(src2)\n+ updateFile(True, aSha, aMode, path, cleanCache)\n+ updateFile(False, sha, mode, path, cleanCache, True)\n else:\n die(\"ERROR: Fatal merge failure, shouldn't happen.\")\n \n"},{"id":"8940","messageId":"7vek7kfqs2.fsf@assigned-by-dhcp.cox.net","threadId":"1743","inReplyTo":"20050919161312.GB1782@c165.ib.student.liu.se","subject":"Re: Yet another set of merge test cases from the kernel tree.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-20T01:53:49Z","receivedAt":"2005-09-20T01:53:49Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> ... The support for\n> renames is currently interleaved with other unrelated changes and\n> this patch should not yet be considered for inclusion. With the rename\n> patch we get clean merges that matches the actual commit for all of\n> those except for 46f5.... git-merge-recursive.py do not merge\n> 46f5... cleanly with the rename patch applied.\n\nThat is very interesting.\n\n> +getFilesRE = re.compile('([0-9]+) ([a-z0-9]+) ([0-9a-f]{40})\\t(.*)')\n> +def mergeTrees(head, merge, common, branch1Name, branch2Name,\n> + cleanCache):\n> ...\n> + if cleanCache:\n> + updateArg = '-i'\n> + else:\n> + updateArg = '-u'\n> +\n> + runProgram(['git-read-tree', updateArg, '-m', common, head, merge])\n\nIt _might_ make sense if we make '-i' and '-u' imply instead of\nrequire '-m' in read-tree, but that will be an independent\npatch.\n\n> +def mergeFile(path, oSha, oMode, aSha, aMode, bSha, bMode,\n> + branch1Name, branch2Name):\n>...\n> + if aMode == oMode:\n> + mode = bMode\n> + else:\n> + mode = aMode\n\nNote: preferring \"our\" mode if there is a conflict instead of\nbarfing. I do not know which is more useful in practice.\n\n> +\n> + return [sha, mode, clean, merge]\n> +\n> +def updateFile(clean, sha, mode, path, cleanCache, onlyWd=False):\n> + updateCache = not onlyWd and (cleanCache or (not cleanCache and clean))\n> + updateWd = onlyWd or (not cleanCache and clean)\n> +\n> + if updateWd:\n> + prog = ['git-cat-file', 'blob', sha]\n> + if stat.S_ISREG(mode):\n> + try:\n> + os.unlink(path)\n> + except OSError:\n> + pass\n> + if mode & 0100:\n> + mode = 0777\n> + else:\n> + mode = 0666\n> + fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)\n> + proc = subprocess.Popen(prog, stdout=fd)\n> + proc.wait()\n> + os.close(fd)\n> + elif stat.S_ISLNK(mode):\n> + linkTarget = runProgram(prog)\n> + os.symlink(linkTarget, path)\n> + else:\n> + assert(False)\n\nCould it happen trying to update a file 'foo' when the working\ntree has 'foo/bar' file (i.e. D/F conflict)?\n\n> +def getRenames(treeOrig, tree):\n>...\n> +def processRenames(entries, renamesA,...\n>...\n\nThese are indeed very interesting.\n"},{"id":"8971","messageId":"20050920055022.GB12979@c165.ib.student.liu.se","threadId":"1743","inReplyTo":"7vek7kfqs2.fsf@assigned-by-dhcp.cox.net","subject":"Re: Yet another set of merge test cases from the kernel tree.","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-20T05:50:22Z","receivedAt":"2005-09-20T05:50:22Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Mon, Sep 19, 2005 at 06:53:49PM -0700, Junio C Hamano wrote:\n> Fredrik Kuivinen writes:\n> \n> > +def mergeFile(path, oSha, oMode, aSha, aMode, bSha, bMode,\n> > + branch1Name, branch2Name):\n> >...\n> > + if aMode == oMode:\n> > + mode = bMode\n> > + else:\n> > + mode = aMode\n> \n> Note: preferring \"our\" mode if there is a conflict instead of\n> barfing. I do not know which is more useful in practice.\n> \n\nI just realized that this piece of code is broken with respect to type\nchanges. Trying to merge a symlink with a file should give us a\nconflict.\n\n> > +\n> > + return [sha, mode, clean, merge]\n> > +\n> > +def updateFile(clean, sha, mode, path, cleanCache, onlyWd=False):\n> > + updateCache = not onlyWd and (cleanCache or (not cleanCache and clean))\n> > + updateWd = onlyWd or (not cleanCache and clean)\n> > +\n> > + if updateWd:\n> > + prog = ['git-cat-file', 'blob', sha]\n> > + if stat.S_ISREG(mode):\n> > + try:\n> > + os.unlink(path)\n> > + except OSError:\n> > + pass\n> > + if mode & 0100:\n> > + mode = 0777\n> > + else:\n> > + mode = 0666\n> > + fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)\n> > + proc = subprocess.Popen(prog, stdout=fd)\n> > + proc.wait()\n> > + os.close(fd)\n> > + elif stat.S_ISLNK(mode):\n> > + linkTarget = runProgram(prog)\n> > + os.symlink(linkTarget, path)\n> > + else:\n> > + assert(False)\n> \n> Could it happen trying to update a file 'foo' when the working\n> tree has 'foo/bar' file (i.e. D/F conflict)?\n> \n\nWe get a list of all files and directories in getFilesAndDirs. This\nlist is then used in processEntry to check for d/f conflicts, so it\nshouldn't happen in that case.\n\nThe rename path do currently not check for d/f conflicts so it could\nprobably happen there.\n\n- Fredrik\n"}]}