{"thread":{"id":"27669","subject":"git-union-merge proposal","startedAt":"2011-06-21T02:20:49Z","lastAt":"2011-06-21T20:19:28Z","messageCount":8,"participants":["Joey Hess","Jonathan Nieder","Johan Herland","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"170347","messageId":"20110621022049.GA1632@gnu.kitenet.net","threadId":"27669","inReplyTo":null,"subject":"git-union-merge proposal","fromName":"Joey Hess","fromEmail":"joey@kitenet.net","sentAt":"2011-06-21T02:20:49Z","receivedAt":"2011-06-21T02:20:49Z","isPatch":false,"sender":{"key":"joey@kitenet.net","avatar":"https://avatars.githubusercontent.com/u/16392?v=4"},"body":"Lately some tools are storing data in git branches or refs, that is not\nsource code, and that is designed in some way to be automatically\nmerged. Generally merge=union will work for it, but the problem is that\ngit-merge can only operate on the checked out branch, not other\nbranches.\n\nSo these things all deal with merging in their own ad-hoc ways:\n\n* pristine-tar commits the info it needs to reconstruct tarballs\n  to a pristine-tar branch; files in the branch should not easily conflict\n  as each includes the name of the tarball.. but when git pull\n  cannot fast-forward the pristine-tar branch, the user is left to\n  manually fix it.\n* git-annex stores location tracking information to log files in\n  .git-annex/; gitattributes is configured to use merge=union,\n  and the log files have timestamps or are otherwise structured to be\n  safely merged.\n* git notes merge -s cat_sort_uniq\n  Notes are stored in a tree using the object sha, which can be\n  union merged, when the notes' format is a series of independant lines.\n* probably other tools do things like this too, or will ...\n\nSo I've written a prototype of a git-union-merge that could be used\nfor all of these. It works like this:\n\ngit union-merge foo origin/foo refs/heads/foo \n\nThat looks up foo and origin/foo and union merges them together,\nproducing the new branch refs/heads/foo. New blobs are injected\nas needed for unioned files, and the merge commit is generated,\nwithout affecting the current working tree, and without any\nexpensive checkouts of the branches. It's pretty fast, it only\nneeds to write out a temporary index file.\n\nPrototype is attached, I doubt it would be suitable for git as-is,\nbut it does show how this is accomplished, if you've not already\nseen how to do it -- just look for ls-tree, diff-tree,\nshow, hash-object, and update-index. Note that merging file modes is\nnot yet dealt with.\n\nI imagine a git that can have union merge or other custom automated\nmerge strategies configured on a per-branch basis, so that git pull\nautomatically merges branches. That could be a good basis for adding\nFossil-like features to git.\n\n-- \nsee shy jo\n\n\n{- git-union-merge program\n -\n - Copyright 2011 Joey Hess <joey@kitenet.net>\n -\n - Licensed under the GNU GPL version 3 or higher.\n -}\n\nimport System.Environment\nimport System.FilePath\nimport System.Directory\nimport System.Cmd.Utils\nimport System.Posix.Env (setEnv)\nimport Control.Monad (when)\nimport Data.List\nimport Data.Maybe\nimport Data.String.Utils\n\nimport qualified GitRepo as Git\nimport Utility\n\nheader :: String\nheader = \"Usage: git-union-merge ref ref newref\"\n\nusage :: IO a\nusage = error $ \"bad parameters\\n\\n\" ++ header\n\nmain :: IO ()\nmain = do\n\t[aref, bref, newref] <- parseArgs\n\tg <- setup\n\tstage g aref bref\n\tcommit g aref bref newref\n\tcleanup g\n\nparseArgs :: IO [String]\nparseArgs = do\n\targs <- getArgs\n\tif (length args /= 3)\n\t\tthen usage\n\t\telse return args\n\ntmpIndex :: Git.Repo -> FilePath\ntmpIndex g = Git.workTree g </> Git.gitDir g </> \"index.git-union-merge\"\n\n{- Configures git to use a temporary index file. -}\nsetup :: IO Git.Repo\nsetup = do\n\tg <- Git.configRead =<< Git.repoFromCwd\n\tcleanup g -- idempotency\n\tsetEnv \"GIT_INDEX_FILE\" (tmpIndex g) True\n\treturn g\n\ncleanup :: Git.Repo -> IO ()\ncleanup g = do\n\te' <- doesFileExist (tmpIndex g)\n\twhen e' $ removeFile (tmpIndex g)\n\n{- Stages the content of both refs into the index. -}\nstage :: Git.Repo -> String -> String -> IO ()\nstage g aref bref = do\n\t-- Get the contents of aref, as a starting point.\n\tls <- fromgit\n\t\t[\"ls-tree\", \"-z\", \"-r\", \"--full-tree\", aref]\n\t-- Identify files that are different between aref and bref, and\n\t-- inject merged versions into git.\n\tdiff <- fromgit\n\t\t[\"diff-tree\", \"--raw\", \"-z\", \"-r\", \"--no-renames\", \"-l0\", aref, bref]\n\tls' <- mapM mergefile (pairs diff)\n\t-- Populate the index file. Later lines override earlier ones.\n\ttogit [\"update-index\", \"-z\", \"--index-info\"]\n\t\t(join \"\\0\" $ ls++catMaybes ls')\n\twhere\n\t\tfromgit l = Git.pipeNullSplit g (map Param l)\n\t\ttogit l content = Git.pipeWrite g (map Param l) content\n\t\t\t>>= forceSuccess\n\t\ttofromgit l content = do\n\t\t\t(h, s) <- Git.pipeWriteRead g (map Param l) content\n\t\t\tlength s `seq` do\n\t\t\t\tforceSuccess h\n\t\t\t\tGit.reap\n\t\t\t\treturn ((), s)\n\n\t\tpairs [] = []\n\t\tpairs (_:[]) = error \"parse error\"\n\t\tpairs (a:b:rest) = (a,b):pairs rest\n\t\t\n\t\tnullsha = take shaSize $ repeat '0'\n\t\tls_tree_line sha file = \"100644 blob \" ++ sha ++ \"\\t\" ++ file\n\t\tunionmerge = unlines . nub . lines\n\t\t\n\t\tmergefile (info, file) = do\n\t\t\tlet [_colonamode, _bmode, asha, bsha, _status] = words info\n\t\t\tif bsha == nullsha\n\t\t\t\tthen return Nothing -- already staged from aref\n\t\t\t\telse mergefile' file asha bsha\n\t\tmergefile' file asha bsha = do\n\t\t\tlet shas = filter (/= nullsha) [asha, bsha]\n\t\t\tcontent <- Git.pipeRead g $ map Param (\"show\":shas)\n\t\t\tsha <- getSha \"hash-object\" $\n\t\t\t\ttofromgit [\"hash-object\", \"-w\", \"--stdin\"] $\n\t\t\t\t\tunionmerge content\n\t\t\treturn $ Just $ ls_tree_line sha file\n\n{- Commits the index into the specified branch. -}\ncommit :: Git.Repo -> String -> String -> String -> IO ()\ncommit g aref bref newref = do\n\ttree <- getSha \"write-tree\"  $\n\t\tpipeFrom \"git\" [\"write-tree\"]\n\tsha <- getSha \"commit-tree\" $\n\t\tpipeBoth \"git\" [\"commit-tree\", tree, \"-p\", aref, \"-p\", bref]\n\t\t\t\"union merge\"\n\tGit.run g \"update-ref\" [Param newref, Param sha]\n\n{- Runs an action that causes a git subcommand to emit a sha, and strips\n   any trailing newline, returning the sha. -}\ngetSha :: String -> IO (a, String) -> IO String\ngetSha subcommand a = do\n\t(_, t) <- a\n\tlet t' = if last t == '\\n'\n\t\tthen take (length t - 1) t\n\t\telse t\n\twhen (length t' /= shaSize) $\n\t\terror $ \"failed to read sha from git \" ++ subcommand ++ \" (\" ++ t' ++ \")\"\n\treturn t'\n\nshaSize :: Int\nshaSize = 40\n"},{"id":"170351","messageId":"20110621052211.GA16919@elie","threadId":"27669","inReplyTo":"20110621022049.GA1632@gnu.kitenet.net","subject":"Re: git-union-merge proposal","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-06-21T05:22:34Z","receivedAt":"2011-06-21T05:22:34Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi Joey,\n\nJoey Hess wrote[1]:\n\n> * git-annex stores location tracking information to log files in\n>   .git-annex/; gitattributes is configured to use merge=union,\n>   and the log files have timestamps or are otherwise structured to be\n>   safely merged.\n> * git notes merge -s cat_sort_uniq\n>   Notes are stored in a tree using the object sha, which can be\n>   union merged, when the notes' format is a series of independant lines.\n> * probably other tools do things like this too, or will ...\n>\n> So I've written a prototype of a git-union-merge that could be used\n> for all of these. It works like this:\n>\n> git union-merge foo origin/foo refs/heads/foo \n\nHm, this makes a lot of sense.  Often a person needs a worktree anyway\nto check the merge result for sanity, but as you say, that needn't\nalways be the case.\n\n[...]\n> Prototype is attached, I doubt it would be suitable for git as-is,\n\nDoes the GitRepo module that it uses come from git-annex?\n\nIf the prototype were self-contained, I would encourage you to submit\nit for inclusion under contrib/ so it can evolve and eventually\ngraduate out of there.  Cc-ing Johan (who has no doubt thought through\nthese things in the context of \"git notes\") in case he has thoughts on\nit.\n\nRegards,\nJonathan\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/176119\n"},{"id":"170359","messageId":"201106210934.34025.johan@herland.net","threadId":"27669","inReplyTo":"20110621052211.GA16919@elie","subject":"Re: git-union-merge proposal","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2011-06-21T07:34:33Z","receivedAt":"2011-06-21T07:34:33Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Tuesday 21 June 2011, Jonathan Nieder wrote:\n> Joey Hess wrote[1]:\n> > * git notes merge -s cat_sort_uniq\n> > \n> >   Notes are stored in a tree using the object sha, which can be\n> >   union merged, when the notes' format is a series of independant\n> >   lines.\n> > \n> > [...]\n> > \n> > So I've written a prototype of a git-union-merge that could be used\n> > for all of these. It works like this:\n> > \n> > git union-merge foo origin/foo refs/heads/foo\n> \n> [...]\n> \n> If the prototype were self-contained, I would encourage you to submit\n> it for inclusion under contrib/ so it can evolve and eventually\n> graduate out of there.  Cc-ing Johan (who has no doubt thought through\n> these things in the context of \"git notes\") in case he has thoughts on\n> it.\n\nThanks for the CC.\n\nI must confess that my Haskell skills are exactly nil, but AFAICS the script \ndepends on the filename as the only criteria to identify files that need a \nline-level merge. How does the script deal with renamed and copied files?\n\nIf you depend on the filename only, this script simply will not work for \nnotes. The notes tree reorganizes itself dynamically for optimum \nperformance, and this affects how notes trees can be merged.\n\nE.g. given a note for object 01234567..., this note may exist as \n\"01234567...\" in one notes tree, while it may exist as \"01/234567...\" in a \nbigger notes tree, or even \"01/23/4567...\" in an even bigger notes tree. \nEven though the filenames differ, they all refer to the same note, and you \ncannot merge notes trees correctly without taking that fact into account.\n\nFurthermore, if you (union-)merge two notes trees that both have \n\"01/234567...\", the result does not necessarily belong in \"01/234567...\". It \ncould be that the sum/union of the two notes trees have pushed the number of \nnotes in the result so high that \"01/23/4567...\" is now a more optimal name \nfor this note.\n\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"170395","messageId":"20110621161044.GA8079@gnu.kitenet.net","threadId":"27669","inReplyTo":"201106210934.34025.johan@herland.net","subject":"Re: git-union-merge proposal","fromName":"Joey Hess","fromEmail":"joey@kitenet.net","sentAt":"2011-06-21T16:10:44Z","receivedAt":"2011-06-21T16:10:44Z","isPatch":false,"sender":{"key":"joey@kitenet.net","avatar":"https://avatars.githubusercontent.com/u/16392?v=4"},"body":"Jonathan Nieder wrote:\n> Does the GitRepo module that it uses come from git-annex?\n> \n> If the prototype were self-contained, I would encourage you to submit\n> it for inclusion under contrib/ so it can evolve and eventually\n> graduate out of there.  Cc-ing Johan (who has no doubt thought through\n> these things in the context of \"git notes\") in case he has thoughts on\n> it.\n\nYes, this was written in the context of git-annex. I would probably not want\nto submit the haskell implementation to contrib/, but a shell implementation\ncould be done that would be perhaps less robust, but also less unusual in\nthe context of git's code base.\n\nJohan Herland wrote:\n> I must confess that my Haskell skills are exactly nil, but AFAICS the script \n> depends on the filename as the only criteria to identify files that need a \n> line-level merge. How does the script deal with renamed and copied files?\n> \n> If you depend on the filename only, this script simply will not work for \n> notes.\n\nIt simply depends on filenames. I saw there was additional complexity\nin notes and I don't see how a general purpose merger can handle that.\n(I wish I could just use notes for my application, but I have data that\nis not tied to any one object in git.)\n\nAlthough, this is an obvious extension that would add some flexability\nto handle for files that cannot be merged with a naive union:\n\ngit union-merge foo origin/foo refs/heads/foo -c \"sort * | uniq\"\n\nWhere the files would be passed in as temp files.\n\nHmm, that makes it look not unlike git-filter-branch, except\nit's generating a new commit at the tip. I *think* that filter-branch\ncan't do this.\n\n-- \nsee shy jo\n"},{"id":"170405","messageId":"7v4o3j9izr.fsf@alter.siamese.dyndns.org","threadId":"27669","inReplyTo":"20110621022049.GA1632@gnu.kitenet.net","subject":"Re: git-union-merge proposal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-21T17:44:56Z","receivedAt":"2011-06-21T17:44:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Joey Hess <joey@kitenet.net> writes:\n\n> Lately some tools are storing data in git branches or refs, that is not\n> source code, and that is designed in some way to be automatically\n> merged. Generally merge=union will work for it, but the problem is that\n> git-merge can only operate on the checked out branch, not other\n> branches.\n\nI think linking \"union\" merge too tightly into this is going in a wrong\ndirection. We _could_ do certain merges without using the working tree at\nall, and the design of \"git merge\" has always been to perform the merge\nentirely in index. We do check out the contents of cleanly resolved paths\nthat are different from the merged-into branch to the working tree, but it\nis perfectly fine if we made it optional. We also do write out half-merged\ncontent to the working tree, but that is merely to ask the user to help\nfinishing the merge that is happening in the index (iow, the ultimate goal\nis to let the user say \"git add\" to tell the index what the resolution is,\nand is not to let the user remove <<< === >>> markers in the file in the\nworking tree). If there is no conflict, we should not have to touch the\nworking tree at all, and \"union\" is a very narrow special case that we\ndeclare there is no conflict (even if there was).\n\nIn other words, I would prefer to see something like:\n\n\t$ git merge --index-only [-s <strategy>] <other_branch>\n\nwhich\n\n    (0) does work without any file checked out in the working tree;\n\n    (1) does not update a path in the working tree even if the merge\n        result for the path is different from the original index entry for\n        the path;\n\n    (2) updates the index only when everything cleanly merges (depending\n        on the definition of \"cleanly merges\", e.g. \"union\" may be a lot\n        more lenient than the usual \"text\" merge) and aborts without\n        touching anything if there is a conflict (because --index-only\n        does not allow us to touch working tree to ask the user to resolve\n        the conflict).\n\n\"git merge\" is designed to work without any file checked out in the\nworking tree, by considering a _missing_ file in the working tree as if\nthere is _no change_ to the path during a merge. IOW, we do not say \"you\nhave an uncommitted local removal of a path, which other side tried to\nmodify, hence we stop the merge to protect your local change\".\n\nThis is so that you can do something like this:\n\n\t$ git checkout v1.7.6-rc2^0\n        $ git reset --hard\n\t$ rm -fr .temp-workdir\n\t$ mkdir .temp-workdir\n        $ cd .temp-workdir\n        $ export GIT_DIR=$(git rev-parse --git-dir)\n\t$ export GIT_WORK_TREE=$(pwd) ;# this is optional, I think.\n        $ git merge -s resolve origin/jk/maint-1.7.2-status-ignored\n        Trying really trivial in-index merge...\n        error: Merge requires file-level merging\n        Nope.\n        Trying simple merge.\n        Simple merge failed, trying Automatic merge.\n        Auto-merging Documentation/git-status.txt\n        ERROR: content conflict in Documentation/git-status.txt\n        Auto-merging t/t7508-status.sh\n        ERROR: content conflict in t/t7508-status.sh\n        Auto-merging wt-status.c\n        fatal: merge program failed\n        Automatic merge failed; fix conflicts and then commit the result.\n        : alter .temp-workdir/master|MERGING; ls\n        ./  ../  Documentation/  t/  wt-status.c\n\nBecause .temp-workdir is empty when merge is run, we consider that your\nworking tree exactly matches what is in your index. We do check out the\ncleanly merged result to this temporary working tree (wt-status.c is\ncleanly merged and result can be seen there), but it is not strictly\nnecessary (IOW we could make that part optional). We do write conflicted\nhalf-merge result, as that is the easiest way for the user to help the\nindex resolve it.\n\n    Side Note: the \"recursive\" strategy is so broken that it may assume\n    the working tree has to be populated and the above may not work as\n    nicely.\n\nIn other words, we are already half-way there, I think.\n"},{"id":"170406","messageId":"7vy60v835o.fsf@alter.siamese.dyndns.org","threadId":"27669","inReplyTo":"7v4o3j9izr.fsf@alter.siamese.dyndns.org","subject":"Re: git-union-merge proposal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-21T18:12:19Z","receivedAt":"2011-06-21T18:12:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> In other words, I would prefer to see something like:\n>\n> \t$ git merge --index-only [-s <strategy>] <other_branch>\n>\n> which\n>\n>     (0) does work without any file checked out in the working tree;\n>\n>     (1) does not update a path in the working tree even if the merge\n>         result for the path is different from the original index entry for\n>         the path;\n>\n>     (2) updates the index only when everything cleanly merges (depending\n>         on the definition of \"cleanly merges\", e.g. \"union\" may be a lot\n>         more lenient than the usual \"text\" merge) and aborts without\n>         touching anything if there is a conflict (because --index-only\n>         does not allow us to touch working tree to ask the user to resolve\n>         the conflict).\n>\n> \"git merge\" is designed to work without any file checked out in the\n> working tree, by considering a _missing_ file in the working tree as if\n> there is _no change_ to the path during a merge. IOW, we do not say \"you\n> have an uncommitted local removal of a path, which other side tried to\n> modify, hence we stop the merge to protect your local change\".\n>\n> This is so that you can do something like this:\n> ...\n> In other words, we are already half-way there, I think.\n\nAddendum.\n\nPeople have wished on this list who have two or more branches, e.g. \"work\"\nand \"play\", based on the same upstream branch to be able to do:\n\n\t$ git fetch origin\n\t$ git checkout work\n\t$ git merge @{u}\n        $ git checkout play\n        $ git merge @{u}\n\t$ git checkout work\n\ni.e. integrate upstream changes without having to check out \"play\" branch\nfirst, if there is no conflict. The standard answer has been \"You cannot,\nbecause you may not know if there will be a conflict until you try\".\n\nBut the existing \"merge in a temporary working tree that is empty to start\nwith\" support is a good way to implement it.  You would do something like\nthis after you are on your \"work\" branch and finished merging from its\nupstream (package this up in a \"git simplemerge\" script):\n\n\trm -fr .t && mkdir .t && cd .t &&\n        GIT_DIR=$(git rev-parse --git-dir) &&\n        GIT_INDEX_FILE=$GIT_DIR/temp-index &&\n        GIT_WORK_TREE=$(pwd) &&\n        export GIT_DIR GIT_INDEX_FILE GIT_WORK_TREE &&\n\tsave_head &&\n        git symbolic-ref refs/heads/play HEAD\n        git read-tree play &&\n        (\n\t        git merge --no-commit play@{upstream}\n\t)\n\trestore_head\n\nIf the merge goes well without conflict, you write the temporary index out\nto a tree, create a commit and update the \"play\" branch (save_head should\nsave away the current branch and restore_head should restore it).\n\nIf the merge conflicts, you _could_ ask the user to resolve it in .t/\ndirectory (with these updated GIT_DIR/GIT_INDEX_FILE/GIT_WORK_TREE), write\nthe result out to a tree, create a commit and update the \"play\"\nbranch. This is entirely optional, as the common request is to do this\nonly when the merge is trivial and there is no conflict.\n\nAnd if we are allowed to punt when there is a conflict, we do not need the\ntemporary working tree at all if we had --index-only option.  We only need\nto save and restore the HEAD pointer and the index file so that we can\ncontinue working on the \"work\" branch after we are done.\n\nThis incidentally is the reason why I said \"update the index\" and not\n\"create a commit\" when I specified the behaviour of \"--index-only\" in the\nprevious message.\n"},{"id":"170408","messageId":"20110621184101.GA12108@gnu.kitenet.net","threadId":"27669","inReplyTo":"7v4o3j9izr.fsf@alter.siamese.dyndns.org","subject":"Re: git-union-merge proposal","fromName":"Joey Hess","fromEmail":"joey@kitenet.net","sentAt":"2011-06-21T18:41:01Z","receivedAt":"2011-06-21T18:41:01Z","isPatch":false,"sender":{"key":"joey@kitenet.net","avatar":"https://avatars.githubusercontent.com/u/16392?v=4"},"body":"Junio C Hamano wrote:\n> In other words, I would prefer to see something like:\n> \n> \t$ git merge --index-only [-s <strategy>] <other_branch>\n\nWould this allow merging changes into a branch other than HEAD? If so, I\nagree, I'd prefer to see it in git-merge itself if possible.\n\n-- \nsee shy jo\n"},{"id":"170425","messageId":"7vaadb6ipb.fsf@alter.siamese.dyndns.org","threadId":"27669","inReplyTo":"20110621184101.GA12108@gnu.kitenet.net","subject":"Re: git-union-merge proposal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-21T20:19:28Z","receivedAt":"2011-06-21T20:19:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Joey Hess <joey@kitenet.net> writes:\n\n> Junio C Hamano wrote:\n>> In other words, I would prefer to see something like:\n>> \n>> \t$ git merge --index-only [-s <strategy>] <other_branch>\n>\n> Would this allow merging changes into a branch other than HEAD? If so, I\n> agree, I'd prefer to see it in git-merge itself if possible.\n\nI just said \"I would prefer to see\", so allowing or not allowing is up to\nyou ;-).  If course I would prefer to see it not touch HEAD so that your\nworking envirnoment (checked out branch and the working tree) are not\ndisrupted.  See my other message in the thread.\n"}]}