{"thread":{"id":"4407","subject":"[RFC] revision limiter in git-rev-list","startedAt":"2006-06-06T08:36:31Z","lastAt":"2006-06-06T18:29:13Z","messageCount":5,"participants":["Marco Costalba","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"21311","messageId":"e5bfff550606060136l59143ef2mdb9dc68ab78e9ff1@mail.gmail.com","threadId":"4407","inReplyTo":null,"subject":"[RFC] revision limiter in git-rev-list","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-06-06T08:36:31Z","receivedAt":"2006-06-06T08:36:31Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"We currently can run something like\n\ngit-rev-list --topo-order --parents HEAD -- foo1.c foo2.c foo3.c\n\nAnd have in output a list of revisions that modify paths foo1.c,\nfoo2.c and foo.3\n\nFor each revision we have also the corresponding pseudo-parents,\ni.e. the proper parents chosen among the revisions in output list.\n\nThe idea is to extend this behaviour to also commit objects sha.\n\nAs example, given the following revisions history:\n\na\nb-\n| c\n| d\ne\nf\n\nWe could add a new option --filtered so that\n\ngit-rev-list --topo-order --filtered HEAD -- a d e\n\nGives the following\n\na\nb-\n| d\ne\n\nNote that the merge point b has been added implicitly as in path limiter case.\n\n\nThis is a powerful and quite general option that can be use for a large\nand interesting number of cases.\n\n1) Get the branch a given belongs\n\ngit-rev-list --topo-order --parents --filtered\n HEAD -- branchList[0] branchList[1]... branchList[k-1]\n\n\nwhere branchList[] is the vector of branches of lenght k\n\nSearched branch is the one where sha appears as one of his parents.\n\n\n\n2) Get nearest previous tag of a given \n\n\ngit-rev-list --topo-order --parents -n1 --filtered\n -- tagList[0] tagList[1]... tagList[n-1]\n\n\nwhere tagList[] is the vector of tags of lenght n\n\nIn output we have only one revision (see option -n1) that is ,\nhis parent(s) are the nearest tag(s).\n\n\n3) Get tag/branch history with a sensible graph (using a GUI frontend)\n\ngit-rev-list --topo-order --parents --filtered HEAD -- tagList[0] ...\nbranchList[n-1]\n\ngit-rev-list --topo-order --parents --filtered HEAD -- branchList[0]\n... branchList[n-1]\n\n\n4) Filter/find revisions according to a given search criteria (using a\nGUI frontend)\n\ngit-rev-list --topo-order --parents --filtered HEAD -- matchList[0]\n... matchList[n-1]\n\nwhere matchList[] is the vector of sha's matching a filter criteria and could\nbe provided by a GUI frontend that already normally have filter capabilities.\n\nThe plus here is to let frontend to draw a sensible graph of the\nresulting revisions.\n\nProbably there are other uses of this option that is very powerful\nbecause essentially\nit adds topological information to a given set of revisions.\n\nOf course I really ignore any implementation difficult/feasibility issues ;-)\n\n\nMarco\n"},{"id":"21313","messageId":"7v7j3uvapa.fsf@assigned-by-dhcp.cox.net","threadId":"4407","inReplyTo":"e5bfff550606060136l59143ef2mdb9dc68ab78e9ff1@mail.gmail.com","subject":"Re: [RFC] revision limiter in git-rev-list","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-06T10:29:37Z","receivedAt":"2006-06-06T10:29:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" writes:\n\n> Of course I really ignore any implementation difficult/feasibility issues ;-)\n\nI do not think your problem is ignoring difficulty/feasibility.\nThe bigger problem is ignoring to describe the semantics of what\nyou are proposing.\n\nFor example:\n\n> As example, given the following revisions history:\n>\n> a\n> b-\n> | c\n> | d\n> e\n> f\n>\n> We could add a new option --filtered so that\n>\n> git-rev-list --topo-order --filtered HEAD -- a d e\n>\n> Gives the following\n>\n> a\n> b-\n> | d\n> e\n\nWhy does it give that? Where is the HEAD in the example, and\nhow does it affect the result? I presume when you wrote the\nunfiltered graph, you meant time flows from top to bottom. In\nother words, I would have written the original graph like this,\ntime flowing from left to right:\n\n c---d\n /\n a---b---e---f\n\nDoes your rev-list given above give different results depending\non HEAD being d or f? If so how, and for which case is the\nexample output produced? If not, what significance does the\nHEAD argument have in the algorithm that generates the result\nyou are proposing (maybe your example had time flowing from\nbottom to top, then the HEAD might be at a, and you did not have\nto think about this question when you wrote the message)? These\nare rhetorical questions, so do not waste time thinking about\nanswers to them before reading to the end of this message.\n\n> Note that the merge point b has been added implicitly as in\n> path limiter case.\n\nI do not think path limiter case adds anything. A merge is\nshown if it touches the path in an nontrivial way, but otherwise\nit isn't. Also b is not a merge unless time is flowing from\nbottom to top in your picture -- it is a fork point.\n\nWhile I really do not think this belongs to rev-list, I suspect\nwhat you want is a command that takes a set of commits you are\ninterested in and gives you an abbreviated topology across them.\nI think it might be a good thing to have in our toolset (didn't\nI say that already?).\n\nSo your example would become:\n\n Given this graph (and there may be other nodes before a or after\n d or f):\n\n c---d\n /\n a---b---e---f\n\n\tthe user is interested in A, D, and E. Show an\n\tabbreviated topology containing them.\n\nwhich would give you\n\n D\n /\n A---B---E\n\nBTW, interestingly enough if the time flowed from right to left,\nthe answer is the same here.\n\nThe command line would not involve HEAD unless it is also one of\nthe commits you are interested in. So it would be something\nlike:\n\n\tgit graph-reduce A D E\n\nwhich would give you:\n\n\tE B\n D B\n B A\n\nor even (since you are interested in reachability):\n\n\tE B A\n D B A\n B A\n\nUnfortunately, your description is a bit too fuzzy to me, so I\nam making guesses as to what you really want. For example,\nalthough you said \"b is included because it is a merge\", I\nstrongly suspect you have cases where you would want to and not\nwant to include a fork point or a merge point in the result,\ndepending on the commits you are interested in. If you are\nreducing this graph for A, H, and J:\n\n f---g\n / \\\n c---d---e---h\n / \n\ta---b---i---j\n\nI think you would want to see this as the result of graph\nreduction:\n\n H\n / \n\tA---B---J\n\ninstead of:\n\n C---E---H\n / \n A---B---J\n\nThat is, although e is a merge and c is a fork point, they do\nnot bring anything interesting in the bird's eye view picture,\nand are filtered out. However, b is a point where lines of\ndevelopment leading to H and J (two of the commits the user is\ninterested in) forks, and it is interesting.\n\nIs this kind of graph reduction what you are after?\n"},{"id":"21314","messageId":"e5bfff550606060414h37099bc1u770c204c269ebad6@mail.gmail.com","threadId":"4407","inReplyTo":"7v7j3uvapa.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFC] revision limiter in git-rev-list","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-06-06T11:14:36Z","receivedAt":"2006-06-06T11:14:36Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 6/6/06, Junio C Hamano wrote:\n> \"Marco Costalba\" writes:\n>\n> > Of course I really ignore any implementation difficult/feasibility issues ;-)\n>\n> I do not think your problem is ignoring difficulty/feasibility.\n> The bigger problem is ignoring to describe the semantics of what\n> you are proposing.\n>\n\nSadly I have to agree, sorry.\n\n> For example:\n>\n> > As example, given the following revisions history:\n> >\n> > a\n> > b-\n> > | c\n> > | d\n> > e\n> > f\n> >\n> > We could add a new option --filtered so that\n> >\n> > git-rev-list --topo-order --filtered HEAD -- a d e\n> >\n> > Gives the following\n> >\n> > a\n> > b-\n> > | d\n> > e\n>\n> Why does it give that? Where is the HEAD in the example,\n\nHEAD is \"a\", just to try to be more clear that's the graph you would see running\ngitk HEAD: HEAD is at top (\"a\") initial revision is at bottom (\"e\").\n\n>\n> > Note that the merge point b has been added implicitly as in\n> > path limiter case.\n>\n> I do not think path limiter case adds anything. A merge is\n> shown if it touches the path in an nontrivial way, but otherwise\n> it isn't.\n\nYes.\n\n>Also b is not a merge unless time is flowing from\n> bottom to top in your picture -- it is a fork point.\n>\n\nI meant a graph as shown by gitk HEAD, so I really meant\n\"b\" is a merge.\n\n\n> While I really do not think this belongs to rev-list, I suspect\n> what you want is a command that takes a set of commits you are\n> interested in and gives you an abbreviated topology across them.\n> I think it might be a good thing to have in our toolset (didn't\n> I say that already?).\n>\n> So your example would become:\n>\n> Given this graph (and there may be other nodes before a or after\n> d or f):\n>\n> c---d\n> /\n> a---b---e---f\n>\n> the user is interested in A, D, and E. Show an\n> abbreviated topology containing them.\n>\n> which would give you\n>\n> D\n> /\n> A---B---E\n>\n\nYes.\n\n>\n> Unfortunately, your description is a bit too fuzzy to me, so I\n> am making guesses as to what you really want. For example,\n> although you said \"b is included because it is a merge\", I\n> strongly suspect you have cases where you would want to and not\n> want to include a fork point or a merge point in the result,\n> depending on the commits you are interested in. If you are\n> reducing this graph for A, H, and J:\n>\n> f---g\n> / \\\n> c---d---e---h\n> /\n> a---b---i---j\n>\n> I think you would want to see this as the result of graph\n> reduction:\n>\n> H\n> /\n> A---B---J\n>\n> instead of:\n>\n> C---E---H\n> /\n> A---B---J\n>\n> That is, although e is a merge and c is a fork point, they do\n> not bring anything interesting in the bird's eye view picture,\n> and are filtered out. However, b is a point where lines of\n> development leading to H and J (two of the commits the user is\n> interested in) forks, and it is interesting.\n>\n> Is this kind of graph reduction what you are after?\n>\n>\n\nPractically speaking it's the kind of reduction for whom examples I\ngave _do_ work.\n\n\n Marco\n"},{"id":"21315","messageId":"e5bfff550606060446rc9160cbt948ceededeb22766@mail.gmail.com","threadId":"4407","inReplyTo":"7v7j3uvapa.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFC] revision limiter in git-rev-list","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-06-06T11:46:23Z","receivedAt":"2006-06-06T11:46:23Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":">\n> While I really do not think this belongs to rev-list, I suspect\n> what you want is a command that takes a set of commits you are\n> interested in and gives you an abbreviated topology across them.\n\n\nI was thinking at an extension of git-rev-list because\n\n1) Current git-rev-list options are quite orthogonal with rev limiter.\nAs example in previous given examples -n and --parents options are\nused and I think more could be used with\ninteresting results.\n\nCurrent git-rev-list options are a lot and are very powerful, it's a\npity if this new feature do not inherit them.\n\n2) This feature could be seen as a generalization of path limiting.\n\n>From today:\n git-rev-list HEAD -- ... \n\nTo possible:\ngit-rev-list HEAD -- ... \n\nWhere obj == || obj == || obj == \n\nOf course we need a (syntactic) way to disambiguate the arguments\nafter '--' but the results are very powerful and general, as example\nwe could mix commit objects _and_ paths in git-rev-list command line\n(git-rev-list HEAD -- foo.c tag1) and also be able to use the full\nset of git-rev-list options before the '--'\n\n\n Marco\n"},{"id":"21334","messageId":"7vu06yp286.fsf@assigned-by-dhcp.cox.net","threadId":"4407","inReplyTo":"e5bfff550606060446rc9160cbt948ceededeb22766@mail.gmail.com","subject":"Re: [RFC] revision limiter in git-rev-list","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-06T18:29:13Z","receivedAt":"2006-06-06T18:29:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" writes:\n\n> I was thinking at an extension of git-rev-list because\n>\n> 1) Current git-rev-list options are quite orthogonal with rev limiter.\n\nWhich means you have to think through what you want to happen\nwhen the user uses various other existing features.\n\nFor example, let's say you want to make this work together with\npath limiting. I have not thought things through, especially\naround merges and fork points, but I suspect that it could be\nimplemented by having a new postprocessing phase:\n\n - Get the list of commits we are interested in from the command\n line.\n\n - Teach revision.c::try_to_simplify_commit() not to drop the\n commit from the simplified ancestry chain when such a list\n exists.\n\n This would probably involve disabling the code to do merge\n simplification, which would make rev-list much less useful\n while working in this mode.\n\n - At the end of revision.c::limit_list(), before we compute\n boundary commits perhaps, look at the resulting list and drop\n single-parent commits from the ancestry chain that are not in\n the \"interesting\" set.\n\nWhen viewed this way, this thing is not a \"rev limiter\", but\nmore like \"I want you keep these even if they are usually\ndropped otherwise\" -- \"rev keeper\" perhaps. That is why I said\nI suspect what you want is a graph reduction and not necessarily\nsomething that interacts with rev-list.\n\nOn the other hand, you may not mind (or you may even prefer) the\nalgorithm not to show commits in your \"rev limiter\" set if they\ndo not touch the specified paths. You do not have to butcher\ntry_to_simplify_commit() but only need the postprocessing, if\nthat is the case. I cannot tell which one you wanted.\n\nBy the way, I have become quite unsure about the extra inclusion\nof merge and fork-point. I said:\n\n> I think you would want to see this as the result of graph\n> reduction:\n>\n> H\n> /\n> A---B---J\n>\n> That is, although e is a merge and c is a fork point, they do\n> not bring anything interesting in the bird's eye view picture,\n> and are filtered out. However, b is a point where lines of\n> development leading to H and J (two of the commits the user is\n> interested in) forks, and it is interesting.\n\nBut I now think what is reasonable to give might be this instead:\n\n H\n /\n\tA---J\n\nOften, the topic-branch workflow involves many merges between\ntopic and master. I will depict just one criss-cross pair here,\nbut in practice there will be several, mostly merging \"so far\nthis is good\" part from topic to master:\n\n o---o---o---o---o---o---o---o \"topic\" \n / \\ /\n o---o---o---o---o---o---o---o---o \"master\"\n\nWhen I say I am interested in viewing a reduced topology around\n\"topic\" and \"master\", I could end up getting:\n\n .---*-------*---* \"topic\" \n / \\ /\n ---*-------*---*---* \"master\"\n\nwith many cross bridges. I am not sure why I am interested in\nthese cross bridges more than I am interested in the commits\nthat do the real work to introduce changes to the topic and\nmaster (i.e. single parent commits). It is _interesting_ to\nsee, but I consider it is more of a curiosity than of a real\nvalue in understanding what happened in the development\nhistory.\n\nOn the other hand, if we say we are interested in seeing the\nskeleton picture, I am not sure what is reasonable to draw when\nyour topic needed a merge from another topic because they are\nsomewhat related:\n\n\n o---o---o---o---o---o \"another topic\"\n / \\\n / o---o---o---X---o---o---o---o \"topic\"\n / / \\ /\n o---o---o---o---o---o---o---o---o---o \"master\"\n\nNow, when you say \"I am interested in seeing how topic and\nmaster have evolved\", what would you do with the merge X?\nOne possibility is to do this:\n\n .-------.\n / \\\n / .---*---X---*---* \"topic\" \n / / \\ /\n ---Y---*-------*---*---* \"master\"\n\nBetween X and Y are all the interesting work that are omitted\nfrom the bird's eye view, but nevertheless Y is a fake parent of\nX. Perhaps, this is useful, but I am not so convinced.\n\nI am afraid this is going to be the last message from me on this\ntopic for now, since I'd like to concentrate on getting the\n\"master\" branch in a good shape for 1.4.0 by this weekend and\nwould like to have everybody do the same, and I expect to be\nmostly offline next week. But I think this exchange is bringing\nus closer to have a description of how the various bits in the\ncurrent rev-list are supposed to interact with this new feature,\nmaking it a bit more concrete for us to visualize how it could\nbe made implementable.\n\nThere are other interactions with \"existing bits\" that need to\nbe thought through but I only gave an example and a half of path\nlimiter and merge/fork in this message.\n\nOutput filters (e.g. --max-count) would be easy, but I suspect\nyou would have even more interesting issues when you have\nnegative refs (^A ^B C). I currently do not have any idea how\nyou would do --boundary for this either.\n"}]}