{"thread":{"id":"10493","subject":"New features in gitk","startedAt":"2007-10-28T01:39:34Z","lastAt":"2007-11-16T07:30:55Z","messageCount":57,"participants":["Paul Mackerras","Linus Torvalds","Steffen Prohaska","Pierre Habouzit","Mike Hommey","Jonathan del Strother","Han-Wen Nienhuys","Michele Ballabio","Marco Costalba","Johannes Schindelin","Junio C Hamano","Sven Verdoolaege","Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"57383","messageId":"18211.59478.188419.397886@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":null,"subject":"New features in gitk","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-10-28T01:39:34Z","receivedAt":"2007-10-28T01:39:34Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"I just pulled the dev branch of gitk into the master branch, so the\nmaster branch now has the new features and improvements that I have\nbeen working on, namely:\n\n* The find and highlight functions have been combined into a single\n function, and there is now a button for finding backwards as well as\n a find forwards button. Thus you can now search for commits that\n modify certain files or directories, or commits that add/remove a\n given string, as well as searching for commits by commit message,\n author, committer or headline.\n\n* Combining the find and highlight functions freed up space that is\n now used for a progress bar and a status window.\n\n* There is now a font chooser accessible from the edit/preferences\n window.\n\n* Gitk now uses a new graph layout algorithm, which means it doesn't\n have to generate the whole layout from top to bottom at startup\n time, making startup faster. Gitk also uses a new style for drawing\n short diagonal line segments that join an existing vertical line,\n which is visually clearer when the segment crosses another line.\n\n* Gitk caches the topology information used for the previous/next tag\n and branch information, making startup faster.\n\nTk 8.5 is now in beta, meaning that some distros now have it\npackaged. Gitk looks much nicer in Tk8.5 since it supports\nanti-aliased fonts, so I strongly suggest that people install and use\nTk8.5 if possible.\n\nPaul.\n"},{"id":"57386","messageId":"alpine.LFD.0.999.0710272229430.30120@woody.linux-foundation.org","threadId":"10493","inReplyTo":"18211.59478.188419.397886@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-28T05:34:01Z","receivedAt":"2007-10-28T05:34:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 28 Oct 2007, Paul Mackerras wrote:\n>\n> I just pulled the dev branch of gitk into the master branch, so the\n> master branch now has the new features and improvements that I have\n> been working on, namely:\n\n*Huge* improvements. It is now really nice to start up gitk even on the \nfull kernel history.\n\nHowever, that crazy green bar chasing back-and-forth int he \"reading\" \nphase is really quite visually distracting. Maybe it looks better in \nTk8.5, but it does look pretty annoying in the version I have. Can you \ntone that down a bit? \n\nBut this has both the layout performance improvements and the fixes to \nonly show selected files in the diff view by default, so I hope this gets \nmerged into standard git soon..\n\n\t\tLinus\n"},{"id":"57390","messageId":"18212.13862.637991.30536@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0710272229430.30120@woody.linux-foundation.org","subject":"Re: New features in gitk","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-10-28T07:11:34Z","receivedAt":"2007-10-28T07:11:34Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> However, that crazy green bar chasing back-and-forth int he \"reading\" \n> phase is really quite visually distracting. Maybe it looks better in \n> Tk8.5, but it does look pretty annoying in the version I have. Can you \n> tone that down a bit? \n\nYeah. Actually what I'd like is to know how many commits git log is\ngoing to give me, so that I can do a normal progress bar whose length\nis proportional to commits_read / total_commits. With --topo-order\n(or --date-order) it has to get to the last commit before it outputs\nthe first commit, doesn't it? So could it print the total number of\ncommits on a line by itself at the start of its output? (Presumably\nit would need a --commit-count flag to enable that behaviour.)\n\nOther than that, I could slow the progress bar down, or do a bar of\nmoving diagonal stripes, or something.\n\nPaul.\n"},{"id":"57398","messageId":"5209A0B4-520E-4EC2-9901-C83C34652313@zib.de","threadId":"10493","inReplyTo":"18212.13862.637991.30536@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Steffen Prohaska","fromEmail":"prohaska@zib.de","sentAt":"2007-10-28T07:36:10Z","receivedAt":"2007-10-28T07:36:10Z","isPatch":false,"sender":{"key":"prohaska@zib.de","avatar":"https://avatars.githubusercontent.com/u/217580?v=4"},"body":"\nOn Oct 28, 2007, at 8:11 AM, Paul Mackerras wrote:\n\n> Linus Torvalds writes:\n>\n>> However, that crazy green bar chasing back-and-forth int he \"reading\"\n>> phase is really quite visually distracting. Maybe it looks better in\n>> Tk8.5, but it does look pretty annoying in the version I have. Can \n>> you\n>> tone that down a bit?\n\nI have the same impression.\n\n\n> Yeah. Actually what I'd like is to know how many commits git log is\n> going to give me, so that I can do a normal progress bar whose length\n> is proportional to commits_read / total_commits.\n\nCan you use something like a rotating wheel, if the total size\nof the task is unknown.\n\nOr if you know an upper bound on the number of expected commits,\nyou could use this as total_commits. And adjust the upper\nbound if more information becomes available.\n\nOr you just print the number of commits already read and the\nuser is happy because something is changing.\n\n\tSteffen\n"},{"id":"57436","messageId":"alpine.LFD.0.999.0710280943090.30120@woody.linux-foundation.org","threadId":"10493","inReplyTo":"18212.13862.637991.30536@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-28T16:50:55Z","receivedAt":"2007-10-28T16:50:55Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 28 Oct 2007, Paul Mackerras wrote:\n>\n> Yeah. Actually what I'd like is to know how many commits git log is\n> going to give me\n\nThat's not known until later.\n\n> With --topo-order (or --date-order) it has to get to the last commit \n> before it outputs the first commit, doesn't it?\n\nThe cost is not generally in outputting the commits. The real cost is in \ntraversing them in the first place. \n\nSo yes, we could output the number of commits once we know it, but \ngenerally, by that time, it's not an interesting number any more! You \nmight as well just read the list, because git is going to feed it to you \nas fast as it can (which is plenty fast - you'll probably get hundreds of \nmegabytes of SHA1 values per second at that point).\n\nSo basically, by the time you start getting SHA1's from --topo-order, the \nbest thing you can do is just lay back and think of England. The *last* \nthing you want to do is bother with any graphics and updates, because it's \njust going to slow things down.\n\nIt's before you even start getting the SHA1's, _or_ if you don't use \n\"--date/topo-order\" in the first place, that you want to have a \"wait, I'm \nthinking\" thing. And at neither time do you know how long it's going to \nbe.\n\n(And as mentioned many times earlier - if you can avoid topo-order and \ndate-order entirely, you are going to perform a million times better at \nstartup for the cold-cache case. Since you seem to be doing the graph \nlayout lazily now, maybe you could aim for that some day? It does mean \nthat you might - occasionally - end up having to add a commit to \n*before* one you already laid out).\n\n\t\tLinus\n"},{"id":"57452","messageId":"20071028183216.GA4310@artemis.corp","threadId":"10493","inReplyTo":"18211.59478.188419.397886@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-10-28T18:32:16Z","receivedAt":"2007-10-28T18:32:16Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On dim, oct 28, 2007 at 01:39:34 +0000, Paul Mackerras wrote:\n> I just pulled the dev branch of gitk into the master branch, so the\n> master branch now has the new features and improvements that I have\n> been working on, namely: [...]\n\nAs you seem to be the guy to ask for, I've a couple of requests wrt\ngitk.\n\n * the diff window is quite bad with merge commits, the colorization is\n rather poor, and the last version you just merged isn't especially\n better.\n\n * the 'sha1' input field is a major pain in the UI: the cut&paste\n interaction is very poor. I don't know why, but it's often very very\n hard to really copy the sha id, probably because it's selected by\n default.\n\n * hjkl in the history list do very very very curious things, whereas I\n would expect j/k to do the same as (resp) down/up. Note that in\n [Help->Key bindings] it's said it should work that way, but it\n doesn't here at least. A way to customize bindings would be much\n appreciated (I like vi bindings, and I miss ^U/^D, and ^E/^Y e.g.).\n\n * I really really really miss an option to ignore whitespaces in\n diffs, a small checkbox to view the full blown diff, or the one\n without spaces changes (-w -b) would be _really_ great.\n\n * the fact that it remembers the position where it was in the WM when\n it was closed is really annoying. the WM is supposed to place the\n window. With at least ion3 and xinerama it often shows up on the\n wrong screen. Remembering the window size though is fine.\n\n * wrt the layout, when the gitk window is resized, the resizing of the\n three columns (subjects, commiter, date) is really cumbersome. I\n would expect that the subject one would be the sole one to be\n resized.\n\n * still wrt the layout, the focus is quite cumbersome. Gitk would be\n really really really nice to be used only from the keyboard, but\n because of a very unclear focus policy, it really isn't for me.\n Maybe it's just me, and I know this may not be 100% helpful, but I\n never know which part of gitk will receive my keys (history part,\n diff part, tree, ...).\n\n * in the diff [lines of context] input, if you hit \"down\" it\n decrements the number of lines which is okay, but _also_ moves the\n selected history line which is not.\n\n\n This list may sound harsh, I hope not, I love gitk, it's one of the\n10 git commands I use the most.\n\nCheers,\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"57453","messageId":"20071028183819.GA20541@glandium.org","threadId":"10493","inReplyTo":"20071028183216.GA4310@artemis.corp","subject":"Re: New features in gitk","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2007-10-28T18:38:19Z","receivedAt":"2007-10-28T18:38:19Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Sun, Oct 28, 2007 at 07:32:16PM +0100, Pierre Habouzit wrote:\n> On dim, oct 28, 2007 at 01:39:34 +0000, Paul Mackerras wrote:\n> > I just pulled the dev branch of gitk into the master branch, so the\n> > master branch now has the new features and improvements that I have\n> > been working on, namely: [...]\n> \n> As you seem to be the guy to ask for, I've a couple of requests wrt\n> gitk.\n(...)\n * When running gitk --all, it would be nice if the current branch\n was selected, instead of the topmost commit.\n\nMike\n"},{"id":"57455","messageId":"18213.6055.235067.730640@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"20071028183216.GA4310@artemis.corp","subject":"Re: New features in gitk","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-10-28T23:13:43Z","receivedAt":"2007-10-28T23:13:43Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Pierre Habouzit writes:\n\n> As you seem to be the guy to ask for, I've a couple of requests wrt\n> gitk.\n> \n> * the diff window is quite bad with merge commits, the colorization is\n> rather poor, and the last version you just merged isn't especially\n> better.\n\nThat's not a request, that's a grizzle. :) What would you like it to\nlook like?\n\n> * the 'sha1' input field is a major pain in the UI: the cut&paste\n> interaction is very poor. I don't know why, but it's often very very\n> hard to really copy the sha id, probably because it's selected by\n> default.\n\nIt's selected so that the contents are in the cut buffer and you can\npaste them in an xterm with middle-button. Possibly I need to check\nthat control-C (or command-C under macos) is properly bound to copy.\n\n> * the fact that it remembers the position where it was in the WM when\n> it was closed is really annoying. the WM is supposed to place the\n> window. With at least ion3 and xinerama it often shows up on the\n> wrong screen. Remembering the window size though is fine.\n\nThat came in with some changes that make gitk start up correctly under\nwindows. I could see about making it set the window position only\nunder windows.\n\n> * still wrt the layout, the focus is quite cumbersome. Gitk would be\n> really really really nice to be used only from the keyboard, but\n> because of a very unclear focus policy, it really isn't for me.\n> Maybe it's just me, and I know this may not be 100% helpful, but I\n> never know which part of gitk will receive my keys (history part,\n> diff part, tree, ...).\n\nWhat focus policy would you like?\n\nPaul.\n"},{"id":"57464","messageId":"20071029062000.GB4310@artemis.corp","threadId":"10493","inReplyTo":"18213.6055.235067.730640@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-10-29T06:20:00Z","receivedAt":"2007-10-29T06:20:00Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Sun, Oct 28, 2007 at 11:13:43PM +0000, Paul Mackerras wrote:\n> Pierre Habouzit writes:\n> \n> > As you seem to be the guy to ask for, I've a couple of requests wrt\n> > gitk.\n> > \n> > * the diff window is quite bad with merge commits, the colorization is\n> > rather poor, and the last version you just merged isn't especially\n> > better.\n> \n> That's not a request, that's a grizzle. :) What would you like it to\n> look like?\n\n I believe that git show/diff has it right: lines with a + should be in\nthe \"added\" color, and lines with a '-' in the \"removed\" one. gitk only\ntake the first \"column\" of +/- into account or sth I find awkward at\nbest, and I often go to the console to see a merge commit because of\nthat.\n\n> > * the 'sha1' input field is a major pain in the UI: the cut&paste\n> > interaction is very poor. I don't know why, but it's often very very\n> > hard to really copy the sha id, probably because it's selected by\n> > default.\n>\n> It's selected so that the contents are in the cut buffer and you can\n> paste them in an xterm with middle-button. Possibly I need to check\n> that control-C (or command-C under macos) is properly bound to copy.\n\n Well, doing ^C doesn't always copy it (probably a glitch wrt which\ninput has the focus), and it certainly doesn't synchronize with the cut\nbuffer for me. And it doesn't work for anyone at work either. I use ion\nwith the KDE clipboard manager (klipper -- because I never managed to\nfind a clipboard manager that is as good yet, not depending upon KDE),\nand at work most people use KDE, with the same klipper. Maybe it's a bad\ninteraction, I should try to use it under gnome or so to see if it is.\n\n> > * the fact that it remembers the position where it was in the WM when\n> > it was closed is really annoying. the WM is supposed to place the\n> > window. With at least ion3 and xinerama it often shows up on the\n> > wrong screen. Remembering the window size though is fine.\n> \n> That came in with some changes that make gitk start up correctly under\n> windows. I could see about making it set the window position only\n> under windows.\n\n That'd be really great.\n\n> > * still wrt the layout, the focus is quite cumbersome. Gitk would be\n> > really really really nice to be used only from the keyboard, but\n> > because of a very unclear focus policy, it really isn't for me.\n> > Maybe it's just me, and I know this may not be 100% helpful, but I\n> > never know which part of gitk will receive my keys (history part,\n> > diff part, tree, ...).\n>\n> What focus policy would you like?\n\n Well, what would make sense (to _me_ at least) would be some shortcuts\nto move to the history panel (say e.g. using F1), or to the diff view\n(using e.g. F2), or in the file list (say F3).\n That would hilight with a black 1px line (like it does for other\ninputs fields) to say that this is the primary window part that takes\nthe keyboard inputs atm. And when doing that, if you press 'down' or\n'up' it would scroll the adequate panel. It's really confusing that the\nkeyboard (or hjkl) right now always make the history change.\n\n This way you can make the difference between the keyboard shortcuts\nthat apply to the focused part of the window (up/down, pgup/pgdown are\nIMHO of that kind), and the one that the user (or the default gitk) has\nassociated to a specific part, no matter if it has the focus. E.g. J/K\n(or for emacsish people ^N/^P) could always move the history, that would\nmake sense.\n\nCheers,\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"57465","messageId":"20071029062445.GA15520@artemis.corp","threadId":"10493","inReplyTo":"18213.6055.235067.730640@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-10-29T06:24:45Z","receivedAt":"2007-10-29T06:24:45Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On dim, oct 28, 2007 at 11:13:43 +0000, Paul Mackerras wrote:\n> Pierre Habouzit writes:\n> \n> > As you seem to be the guy to ask for, I've a couple of requests wrt\n> > gitk.\n> > \n> > * the diff window is quite bad with merge commits, the colorization is\n> > rather poor, and the last version you just merged isn't especially\n> > better.\n> \n> That's not a request, that's a grizzle. :)\n\n Right, would have I known a single word of Tcl, I would have provided\npatches for that long time ago btw :P\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"57474","messageId":"8E362637-5AE6-43DC-890D-78BC6B43BDA1@steelskies.com","threadId":"10493","inReplyTo":"20071029062000.GB4310@artemis.corp","subject":"Re: New features in gitk","fromName":"Jonathan del Strother","fromEmail":"maillist@steelskies.com","sentAt":"2007-10-29T08:31:18Z","receivedAt":"2007-10-29T08:31:18Z","isPatch":false,"sender":{"key":"jon.delstrother@bestbefore.tv","avatar":"https://gravatar.com/avatar/754e21ab701c00e2d21fc261187254c34b2a1c0b959d9ee5be1a295990be3081?d=mp&s=160"},"body":"\nOn 29 Oct 2007, at 06:20, Pierre Habouzit wrote:\n\n> On Sun, Oct 28, 2007 at 11:13:43PM +0000, Paul Mackerras wrote:\n>>> * the 'sha1' input field is a major pain in the UI: the cut&paste\n>>> interaction is very poor. I don't know why, but it's often \n>>> very very\n>>> hard to really copy the sha id, probably because it's \n>>> selected by\n>>> default.\n>>\n>> It's selected so that the contents are in the cut buffer and you can\n>> paste them in an xterm with middle-button. Possibly I need to check\n>> that control-C (or command-C under macos) is properly bound to copy.\n>\n> Well, doing ^C doesn't always copy it (probably a glitch wrt which\n> input has the focus), and it certainly doesn't synchronize with the \n> cut\n> buffer for me. And it doesn't work for anyone at work either. I use \n> ion\n> with the KDE clipboard manager (klipper -- because I never managed to\n> find a clipboard manager that is as good yet, not depending upon KDE),\n> and at work most people use KDE, with the same klipper. Maybe it's \n> a bad\n> interaction, I should try to use it under gnome or so to see if it is.\n>\n\nFWIW, I have exactly the same problem under OS X. I've never figured \nout a pattern that gives a guaranteed copy - I'll try playing around \ntoday and see what I can find.\n\nActually, while I'm here, gitk semi-regularly ignores ⌘Q, which \nought to quit on OS X."},{"id":"57482","messageId":"fg4nf6$tei$1@ger.gmane.org","threadId":"10493","inReplyTo":"18211.59478.188419.397886@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@xs4all.nl","sentAt":"2007-10-29T13:30:04Z","receivedAt":"2007-10-29T13:30:04Z","isPatch":false,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"Paul Mackerras escreveu:\n> I just pulled the dev branch of gitk into the master branch, so the\n> master branch now has the new features and improvements that I have\n> been working on, namely:\n> \n> * The find and highlight functions have been combined into a single\n\nsound extremely cool; I didn't know someone was working on it actively.\n\nCan I misuse this thread to bring a ancient bug under your attention? \nIt is affecting me regularly; see here for the report:\n\n http://article.gmane.org/gmane.comp.version-control.git/48789\n\n\n-- \n Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen\n"},{"id":"57483","messageId":"200710291504.08516.barra_cuda@katamail.com","threadId":"10493","inReplyTo":"18211.59478.188419.397886@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Michele Ballabio","fromEmail":"barra_cuda@katamail.com","sentAt":"2007-10-29T14:04:08Z","receivedAt":"2007-10-29T14:04:08Z","isPatch":false,"sender":{"key":"barra_cuda@katamail.com","avatar":"https://avatars.githubusercontent.com/u/16371673?v=4"},"body":"On Sunday 28 October 2007, Paul Mackerras wrote:\n> * Gitk now uses a new graph layout algorithm, which means it doesn't\n> have to generate the whole layout from top to bottom at startup\n> time, making startup faster.\n\nThis is probably causing gitk to eat my (admittedly old) CPU, sometimes.\n\nFor example, a\n\n\tgitk --all v1.5.2..v1.5.3\n\ngives me problems when I scroll down to about half of the shown history:\nthat is when I reach the sequence of hundreds of \"merge topic branch\ninto next\" commits, and gitk tries hard to display the graph as best\nas it can.\n\nIt can become unresponsive for one second at every PgDown.\n\nOtherwise, gitk is way faster in other (non-pathological)\ncircumstances.\n"},{"id":"57797","messageId":"18217.41899.54812.227152@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0710280943090.30120@woody.linux-foundation.org","subject":"Re: New features in gitk","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-11-01T10:00:11Z","receivedAt":"2007-11-01T10:00:11Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> (And as mentioned many times earlier - if you can avoid topo-order and \n> date-order entirely, you are going to perform a million times better at \n> startup for the cold-cache case. Since you seem to be doing the graph \n> layout lazily now, maybe you could aim for that some day? It does mean \n> that you might - occasionally - end up having to add a commit to \n> *before* one you already laid out).\n\nThe other thing --topo-order does is reorder the commits so that\nrelated commits come together. So far, doing that in Tcl has turned\nout to be much slower than having it done in C (within git log) for\nthe hot-cache case (which I expect is the common case).\n\nI'm now thinking that the best approach would be to have gitk cache\nthe topology, and on startup only read in the part of the graph that\nisn't in the cache. Mostly that will be small and so git log should\nbe fast even in the cold-cache case with --topo-order.\n\nPaul.\n"},{"id":"57803","messageId":"18217.47744.621850.100789@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0710280943090.30120@woody.linux-foundation.org","subject":"Re: New features in gitk","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-11-01T11:37:36Z","receivedAt":"2007-11-01T11:37:36Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> The cost is not generally in outputting the commits. The real cost is in \n> traversing them in the first place. \n\nActually, the biggest cost is still gitk reading in the commits from\ngit log and doing the processing that gitk needs to do on each commit\n(which I have tried to minimize, and is way smaller than it used to\nbe, but is still significant).\n\nIn fact that would go significantly faster if git log could output the\ndata for each commit in a slightly different format. What would be\ngood is to get one header line for each commit in the form:\n\nid flag {parent parent parent...} length\n\nwhere:\n\nid is the 40-char SHA1 for the commit\nflag is normally 1, but is 0 for \"boundary\" commits, 2 for \"left-side\"\n commits (with --merge), or 3 for \"right-side\" commits\nlength is the number of characters of commit data that follow\n (which may differ from the number of bytes, so there would need\n to be agreement on the encoding)\n\nfollowed by the body of the commit (with no null or other separator\ncharacter between commits).\n\nThat would be easier to parse in Tcl, and looks like it would knock\nanother 1.5 seconds off the gitk startup time (for the kernel\nrepository on my G5).\n\nPaul.\n"},{"id":"57837","messageId":"alpine.LFD.0.999.0711010815320.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"18217.41899.54812.227152@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-01T15:16:25Z","receivedAt":"2007-11-01T15:16:25Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 1 Nov 2007, Paul Mackerras wrote:\n> \n> The other thing --topo-order does is reorder the commits so that\n> related commits come together.\n\nIf that's the only reason for using it, then please stop, and use \n\"--first-parent\" instead.\n\n\t\tLinus\n"},{"id":"57841","messageId":"alpine.LFD.0.999.0711010844260.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"18217.47744.621850.100789@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-01T15:47:52Z","receivedAt":"2007-11-01T15:47:52Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 1 Nov 2007, Paul Mackerras wrote:\n>\n> Linus Torvalds writes: \n> > The cost is not generally in outputting the commits. The real cost is in \n> > traversing them in the first place. \n> \n> Actually, the biggest cost is still gitk reading in the commits from\n> git log and doing the processing that gitk needs to do on each commit\n> (which I have tried to minimize, and is way smaller than it used to\n> be, but is still significant).\n\nUmm. I think you're basing all your timings on hot-cache numbers.\n\nThe hot-cache numbers are already pretty damn good. But try this:\n\n\techo 3 > /proc/sys/vm/drop_caches\n\tgitk\n\non a big repository, _especially_ one that isn't totally packed, or on a \nmachine with a slow laptop disk. Just following the commit history is \nreally quite expensive.\n\nTHAT is the problem with --topo-order.\n\n\t\t\tLinus\n"},{"id":"57843","messageId":"alpine.LFD.0.999.0711010910090.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711010844260.3342@woody.linux-foundation.org","subject":"Re: New features in gitk","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-01T16:21:01Z","receivedAt":"2007-11-01T16:21:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 1 Nov 2007, Linus Torvalds wrote:\n> \n> The hot-cache numbers are already pretty damn good. But try this:\n> \n> \techo 3 > /proc/sys/vm/drop_caches\n> \tgitk\n\nActually, do the above with a path limiter, to make it more obvious.\n\nSo try this on the kernel, and you'll see the difference even with a fast \ndisk, and even if it's fully packed:\n\n\techo 3 > /proc/sys/vm/drop_caches\n\ttime git rev-list HEAD drivers/scsi | head -10\n\nand now try it with --topo-order.\n\nI get ten seconds with --topo-order (because it has to traverse the \n*whole* history even to just generate the first ten lines), while the \nnon-topo-order case is *three*times* faster.\n\nOn my laptop, it's even more noticeable. I don't know quite why, but the \nnon-topo-order case is actually faster on my laptop than on my desktop \n(will have to see what's up, but I suspect it's a result of they being at \ndifferent points in history, and just bad luck wrt the top-of-history \nhaving happened to change drivers/scsi or not):\n\n\t[torvalds@t40 linux]$ time git rev-list HEAD drivers/scsi | head -10\n\t..\n\treal 0m0.688s\n\nbut with --topo-order it's much slower:\n\n\t[torvalds@t40 linux]$ time git rev-list --topo-order HEAD drivers/scsi | head -10\n\t..\n\treal 0m17.458s\n\nSee? You shouldn't care about CPU usage, you should care about IO costs! \nThose are the first-order effects.\n\nIn other words, if you can be incremental, we're talking about performance \ndifferences that are orders-of-magnitude. Not ten percent or something \npiddling like that! And the performance improvemens come for the cases \nthat are the _problem_, rather than the cases that already work perfectly \nwell.\n\n\t\t\t\tLinus\n"},{"id":"57964","messageId":"18218.63946.772767.179841@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711010815320.3342@woody.linux-foundation.org","subject":"Re: New features in gitk","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-11-02T10:19:54Z","receivedAt":"2007-11-02T10:19:54Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> If that's the only reason for using it, then please stop, and use \n> \"--first-parent\" instead.\n\nHow would that help? That doesn't list about 2/3 of the commits at\nall.\n\nIn any case, no that's not the only reason. The main reason is that\nit (i.e. --topo-order) spits out the commits in exactly the order that\ngitk wants to display them (of which the bit about parents coming\nafter all their children is a part), and thus reduces the amount of\nprocessing I need to do in Tcl.\n\nPaul.\n"},{"id":"57975","messageId":"e5bfff550711020544h1e9a648apfd268eb549645ccc@mail.gmail.com","threadId":"10493","inReplyTo":"18218.63946.772767.179841@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-11-02T12:44:05Z","receivedAt":"2007-11-02T12:44:05Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 11/2/07, Paul Mackerras wrote:\n>\n> In any case, no that's not the only reason. The main reason is that\n> it (i.e. --topo-order) spits out the commits in exactly the order that\n> gitk wants to display them (of which the bit about parents coming\n> after all their children is a part), and thus reduces the amount of\n> processing I need to do in Tcl.\n>\n\nI have tried to overcome --topo-order in qgit but I found it very\ndifficult, too much for me.\n\nLazily drawing the layout it doesn't mean that you lazy load the data\nfrom git, indeed you load all the git-log output as soon as it\narrives.\n\nAnd if the revisions arrive \"in order\", i.e. if revision A arrive\nbefore revision B it means that A is NOT an ancestor of B, this is of\ngreat help.\n\nWhen drawing the graph assuming that the vector/list of the arrived\nsha is already ordered greatly simplify the whole thing, if we relax\nthis hypothesis then a lot of work should be done before to draw a\ngraph chunk, essentially the GUI tool needs to walk the _entire_ list\nand reorder it by itself _before_ to draw any graph chunk also if very\nsmall.\n\nSo at the end you end up transferring the complete revision walk from\ngit-log to the GUI tool, and (this is the important thing) to be sure\ngraph is always correct you need to perform the walk _before_ drawing\nany stuff.\n\nThe only possible _trick_ I was able to find is to optimistically draw\nthe graph chunk _assuming_ that it is ordered.\n\nThen reorder the list in the background and finally check if the graph\nis correct, if not redraw with correct data.\n\nIf the out of order revisions are rare you end up mimic a fast correct\ndrawing. If are not user will see some flickering at the end of the\nload.\n\nIMHO the above scheme is very complicated and fragile.\n\nJust my two cents.\n\nMarco\n"},{"id":"57987","messageId":"alpine.LFD.0.999.0711020751290.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"18218.63946.772767.179841@cargo.ozlabs.ibm.com","subject":"Re: New features in gitk","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-02T15:03:18Z","receivedAt":"2007-11-02T15:03:18Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 2 Nov 2007, Paul Mackerras wrote:\n> \n> How would that help? That doesn't list about 2/3 of the commits at\n> all.\n\nYeah, you'd have to do all the parent processing on your own, I guess that \nwould be too slow.\n\n> In any case, no that's not the only reason. The main reason is that\n> it (i.e. --topo-order) spits out the commits in exactly the order that\n> gitk wants to display them (of which the bit about parents coming\n> after all their children is a part), and thus reduces the amount of\n> processing I need to do in Tcl.\n\nThe thing is, you shouldn't *care* how long it takes to get 50,000+ \ncommits.\n\nYou're only visualizing ~20 commits at a time. Ignore the rest.\n\nTHAT is the number that is timing-critical. You're optimizing for the \nwrong case - the \"whole history\" thing doesn't matter as much as the \n\"recent history\" does.\n\nSo I bet from a usability standpoint, you'd be *much* better off with \nsomething that might take ten times as long for the whole thing, if the \nfirst thirty lines show up in a third of the time.\n\nIn fact, if you want to really optimize parsing and that is a big issue, \nuse\n\n\tgit log --left-right --parents --pretty=format:\"%m %H %P %an <%ae> %aD\"\n\nwhich will give you a single line per commit. I bet tk is good at reading \nsingle lines. Don't even read anythign else - until somebody actually \n*selects* the commit, at which point you do the diff *and* the full thing.\n\nYes, it will make things slower over-all. And no, the above won't work for \nthe \"search everywhere\", which means that once people start searching for \neverything, you'll be screwed, but with somethign like the above, you'll \nget the first commits immediately and can start showing them.\n\nAnd yes, if they come in the wrong order, you'll have to recalculate the \ndisplay, but I thought you had something incremental already - ie you can \nalways do it for just the current window of 100 commits or whatever.\n\n\t\t\tLinus\n"},{"id":"58000","messageId":"alpine.LFD.0.999.0711020828440.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"e5bfff550711020544h1e9a648apfd268eb549645ccc@mail.gmail.com","subject":"Re: New features in gitk","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-02T15:42:58Z","receivedAt":"2007-11-02T15:42:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 2 Nov 2007, Marco Costalba wrote:\n> \n> I have tried to overcome --topo-order in qgit but I found it very\n> difficult, too much for me.\n> \n> Lazily drawing the layout it doesn't mean that you lazy load the data\n> from git, indeed you load all the git-log output as soon as it\n> arrives.\n\nWould it be more palatable if I tried to write some visualization-specific \nfront-end that acted kind of like \"git rev-list\", but would have some way \nof \"resetting\" its output?\n\nThe thing is, I'm pretty sure I can feed you commits really quickly if I \ndon't sort them, and if I don't do the full and careful \"oops, this commit \nwas reachable from a commit that was marked uninteresting\", but while the \nfast-and-stupid approach will work well enough for most things, it will \noccasionally get the wrong answer.\n\nBut it will *notice* when it gets the wrong answer, though, and can reset \nand start over!\n\nIOW, I might be able to do something that\n\n - prints out the commit info per line\n\n - prepends each line with a line number\n\n - goes back to an earlier line 'n' when it notices that it needs to \n output a commit before a previous commit (or when it notices that a \n commit that it had already output was actually not supposed to show up)\n\nand with something like that, I could make git give you incremental \noutput.\n\nThe thing is, any revision information that requires \"global knowledge\" \nsimply cannot scale. And \"git rev-list --topo-order\" may be fast as hell, \nand I can do it in one second on the kernel archive on my machine, but \nthat's really only true when it's all cached. \n\nIf it's not cached, it will inevitably have to read in every single commit \nif you want a \"final and unchanging ordering\". Which inevitably gets you a \nreally irritating startup latency. That's just fundamental.\n\nOn the other hand, if there is some way to say \"oops, restart\", I can \noptimistically give you a list that is always properly sorted on a *local* \nscale, but then based on later data I might notice that it wasn't right \nglobally and that I need to re-do all or part of it.\n\nBut as mentioned, that requires that side-band data of \"uhhuh, I screwed \nup, let me go back and fix it\".\n\n\t\t\tLinus\n"},{"id":"58007","messageId":"e5bfff550711020950w3b628f24k767127c1ffc54510@mail.gmail.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711020828440.3342@woody.linux-foundation.org","subject":"Re: New features in gitk","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-11-02T16:50:47Z","receivedAt":"2007-11-02T16:50:47Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 11/2/07, Linus Torvalds wrote:\n>\n> But it will *notice* when it gets the wrong answer, though, and can reset\n> and start over!\n>\n> IOW, I might be able to do something that\n>\n> - prints out the commit info per line\n>\n> - prepends each line with a line number\n>\n> - goes back to an earlier line 'n' when it notices that it needs to\n> output a commit before a previous commit (or when it notices that a\n> commit that it had already output was actually not supposed to show up)\n>\n> and with something like that, I could make git give you incremental\n> output.\n>\n\nYes. That's would be easier to implement. Better yet do not give line\nnumbers I already push back each revision sha in a vector according to\narrival order. It's a stack like storing.\n\nSo would be nice if 'git log --restarting' would work like this:\n\n- Output the normal stream of commits according to git log arguments.\nNo line numbers, no fancy additional stuff.\n\n- If '--topo-order' or something similar was given git log checks if a\nwrong output occurs, as example because it founds a revisions that\nshould have been already put out say 'n' revisions before the last\noutputted one.\n\n- In the above case git log outputs a side-band data of \"uhhuh, I screwed\nup, I restart from 'n' revisions before the last one outputted\".\n\n- Then ouput _again_ the stream starting from 'n' revisions earlier.\nNote that not only the new offending revision is trasmitted but *all\nthe revisions* from the out of order one to the remaining.\n\nGiven a vector of 'k' arrived revisions, for me it's far easier simply\nto flush the 'n' tail items in the sha vector and restart again then\n_insert_ in the vector the new out of order one.\n\nThis is because parsing alghoritm is based on an 'append new stuff'\napproach, not 'insert in the middle', so better flush all the tail\nalso if probably the big part of retrasmitted revisions would remain\nthe same.\n\n\nMarco\n\nP.S: The out of bound information should be commit data aligned and\ncould take advantage of the fact that an sha always starts with an\nalphanumeric char value [0..9 a..f]\n\nIOW instead of the commit sha this signal could write something like\n\n'Restarting from -12'\n\nand parsing knows that an sha cannot start with an 'R'. Please note\nthat 'instead of the commit sha' it means in the _exact_ place where\nsha is expected and this is not predefined but depends on the git-log\narguments, so that as example\n\n$git log --with-restart\n\nwould output:\n\ncommit 6959893b0b65ebc68ce2fb524a8ec15a26ca4972\nMerge: 452b800... d279fc1...\nAuthor: Junio C Hamano \nDate: Wed Oct 31 23:53:55 2007 -0700\n\n Merge branch 'sp/mergetool'\n\n * sp/mergetool:\n mergetool: avoid misleading message \"Resetting to default...\"\n mergetool: add support for ECMerge\n mergetool: use path to mergetool in config var mergetool..path\n\ncommit Restart from -7\ncommit 3e4bb087a18435b12eb82116e93af2887578e816\nMerge: 5fb1948... 136e631...\nAuthor: Junio C Hamano \nDate: Thu Nov 1 17:09:08 2007 -0700\n\n Merge branch 'maint'\n\n\n\nwhile\n\n$git log --with-restart --pretty=oneline\n\nwould output\n\n6959893b0b65ebc68ce2fb524a8ec15a26ca4972 Merge branch 'sp/mergetool'\nRestart from -7\n3e4bb087a18435b12eb82116e93af2887578e816 Merge branch 'maint'\n5fb19486e6f4b6d31f33f5a1eab970b244fa2d08 Merge branch 'bk/maint-cvsexportcommit'\n\n\nIn this way this side band info became compatible with _any_ git-log\noutput format as long as the format foreseens the output of the\nrevision sha.\n"},{"id":"58012","messageId":"alpine.LFD.0.999.0711021114390.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711020828440.3342@woody.linux-foundation.org","subject":"Re: New features in gitk","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-02T18:16:37Z","receivedAt":"2007-11-02T18:16:37Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 2 Nov 2007, Linus Torvalds wrote:\n> \n> The thing is, I'm pretty sure I can feed you commits really quickly if I \n> don't sort them, and if I don't do the full and careful \"oops, this commit \n> was reachable from a commit that was marked uninteresting\", but while the \n> fast-and-stupid approach will work well enough for most things, it will \n> occasionally get the wrong answer.\n\nOk, I have a trial patch that doesn't do the replay yet, but at least \nnotices when it outputs a parent that has already been shown.\n\nIn the whole git archive, it happens three times.\n\nIn the kernel archive, it happens twelve times.\n\nI'll try to get it into some kind of usable shape, and send out \nexperimental patches for people to play with.\n\n\t\tLinus\n"},{"id":"58013","messageId":"Pine.LNX.4.64.0711021814270.4362@racer.site","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711020828440.3342@woody.linux-foundation.org","subject":"Re: New features in gitk","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-11-02T18:17:47Z","receivedAt":"2007-11-02T18:17:47Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 2 Nov 2007, Linus Torvalds wrote:\n\n> On Fri, 2 Nov 2007, Marco Costalba wrote:\n> > \n> > I have tried to overcome --topo-order in qgit but I found it very \n> > difficult, too much for me.\n> > \n> > Lazily drawing the layout it doesn't mean that you lazy load the data \n> > from git, indeed you load all the git-log output as soon as it \n> > arrives.\n> \n> Would it be more palatable if I tried to write some \n> visualization-specific front-end that acted kind of like \"git rev-list\", \n> but would have some way of \"resetting\" its output?\n\nHeh, Shawn and I were discussing this when we met in San Jose earlier this \nmonth. The application we had in mind was a common backend for graphical \nrepresentation of the commit graph, which could be used by git gui to show \n(part of) the history. The ultimate goal was a graphical rebase -i.\n\nI would have _loved_ to implement this. Alas, as it appears my choice of \njob was less than brilliant, and even when I have some spare moments at \nthe end of the day, I watch movies to forget the day, instead of \nimplementing this fascinating and useful feature.\n\nCiao,\nDscho\n"},{"id":"58035","messageId":"alpine.LFD.0.999.0711021301200.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711021114390.3342@woody.linux-foundation.org","subject":"[PATCH 0/2] History replay support","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-02T20:31:36Z","receivedAt":"2007-11-02T20:31:36Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOk, this is a rough first draft of avoiding the topological sort up-front, \nand instead incrementally sorting only when actually necessary.\n\nThe first patch is a pure cleanup. Quite frankly, I suspect the old \ntopological sorting code would have worked perfectly fine as-is, but I \ncouldn't really bear to watch it or think about debugging it the way it \nwas before.\n\nThe indirection and other strangeness just blew my tiny little mind, and \nwhile I bet it had some historical reason, I ended up reworking that \nthing. I tried to keep it as similar as humanly possible to the old code \n(because it's easy to get wrong, and because I really didn't want to worry \nabout the toposort itself), but the numbers speak for themselves:\n\n\t 4 files changed, 55 insertions(+), 126 deletions(-)\n\nshould tell you something. And it means that there are no subtle calling \nissues with preconditions for using the toposort etc - you can use it over \nand over again, and it should all be obvious. Knock wood.\n\nThe second diff is the one that actually adds the new feature, and it \nundoes most of the nice statistics of the first one:\n\n\t 5 files changed, 70 insertions(+), 12 deletions(-)\n\nbut we still end up with more deletions than insertions on the whole, \n*and* a new feature.\n\nThe new code is triggered by using the \"--replay\" flag, which will cause \ncertain consistency checks to be done when a commit is shown by the log \nmachinery. In particular:\n\n - if we print out a parent SHA1, and the parent has already been shown, \n that's a topology violation, and causes a replay.\n - if we turn a commit unintersting, and the commit has already been \n shown, that's a \"uninteresting\" violation, and causes a replay.\n\nThe second one I didn't test at all. It's probably hard to trigger, and \nI bet there are bugs there, but this is very much a WIP patch, with the \nhope that people other than me can work on it.\n\nWhen a replay happens, the log code will print out\n\n\tReplay \n\nfor each commit that gets invalidated by the replay, and then start \n*that* part of history anew, with just the required part re-sorted.\n\nShould it print just the number of commits? Perhaps. Play around with \nthis.\n\nAnyway, to give you some kind of idea of the effect of this, in the \ncurrent git tree as it exists in my repo, I get 15 replay events, and if \nyou compare the total log output, you see:\n\n\t[torvalds@woody git]$ wc -l t1 t2\n\t 170191 t1\n\t 178150 t2\n\nwhere \"t1\" is without replays, and \"t2\" is with replays. The replays \nobviously do add lines (the replayed ones), but at least for git, it's on \nthe order of 5% lines replayed.\n\nThe big difference is in the latency:\n\n\ttime git log --parents --topo-order | head\n\treal 0m0.163s\n\nvs\n\n\ttime git log --parents --replay | head\n\treal 0m0.003s\n\nie you can see how the --replay thing starts outputtig commits \nimmediately, because it knows it can just back up and fix any errors that \nhappen.\n\nThat's the good news.\n\nThe bad news is that it doesn't work well in this simplistic form, because \nthere is a O(n**2) behaviour when replays *do* happen, ie we end up having \nreplays within replays, and rather than getting a 5% increase like for git \nitself, for the kernel archive this gets a roughly 50x increase for the \nreplay. So the *latency* still improves dramatically (getting the first \none hundred commits in 0.006 seconds vs 1.076s), but because of the bad \nbehaviour wrt cascading replays, it's not really usable in this form (the \nfull log goes from 8 seconds to 22s when writing to /dev/null - and is \nmuch worse if the receiver actually has to do something about it).\n\nI think the right thing to do wrt this all would be to turn the replay \nlogic into a latency-based one, where it would basically batch things up, \nbut make sure to output something at least every half a second or so. But \nthat's a pretty separate set of logic, so I thought I'd send this out \nas-is for comments..\n\n\t\t\tLinus\n"},{"id":"58036","messageId":"alpine.LFD.0.999.0711021331420.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711021301200.3342@woody.linux-foundation.org","subject":"[PATCH 1/2] Simplify topo-sort logic","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-02T20:32:58Z","receivedAt":"2007-11-02T20:32:58Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n.. by not using quite so much indirection.\n\nThis currently grows the \"struct commit\" a bit, which could be avoided by \nusing a union for \"util\" and \"indegree\" (the topo-sort used to use \"util\" \nanyway, so you cannot use them together), but for now the goal of this was \nto simplify, not optimize.\n\nSigned-off-by: Linus Torvalds \n---\n commit.c | 150 +++++++++++++++++++++---------------------------------------\n commit.h | 20 +--------\n revision.c | 7 +--\n revision.h | 4 +-\n 4 files changed, 55 insertions(+), 126 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex ac24266..c155a49 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -9,22 +9,6 @@\n \n int save_commit_buffer = 1;\n \n-struct sort_node\n-{\n-\t/*\n-\t * the number of children of the associated commit\n-\t * that also occur in the list being sorted.\n-\t */\n-\tunsigned int indegree;\n-\n-\t/*\n-\t * reference to original list item that we will re-use\n-\t * on output.\n-\t */\n-\tstruct commit_list * list_item;\n-\n-};\n-\n const char *commit_type = \"commit\";\n \n static struct cmt_fmt_map {\n@@ -1150,69 +1134,38 @@ struct commit *pop_commit(struct commit_list **stack)\n \treturn item;\n }\n \n-void topo_sort_default_setter(struct commit *c, void *data)\n-{\n-\tc->util = data;\n-}\n-\n-void *topo_sort_default_getter(struct commit *c)\n-{\n-\treturn c->util;\n-}\n-\n /*\n * Performs an in-place topological sort on the list supplied.\n */\n void sort_in_topological_order(struct commit_list ** list, int lifo)\n {\n-\tsort_in_topological_order_fn(list, lifo, topo_sort_default_setter,\n-\t\t\t\t topo_sort_default_getter);\n-}\n-\n-void sort_in_topological_order_fn(struct commit_list ** list, int lifo,\n-\t\t\t\t topo_sort_set_fn_t setter,\n-\t\t\t\t topo_sort_get_fn_t getter)\n-{\n-\tstruct commit_list * next = *list;\n-\tstruct commit_list * work = NULL, **insert;\n-\tstruct commit_list ** pptr = list;\n-\tstruct sort_node * nodes;\n-\tstruct sort_node * next_nodes;\n-\tint count = 0;\n-\n-\t/* determine the size of the list */\n-\twhile (next) {\n-\t\tnext = next->next;\n-\t\tcount++;\n-\t}\n+\tstruct commit_list *next, *orig = *list;\n+\tstruct commit_list *work, **insert;\n+\tstruct commit_list **pptr;\n \n-\tif (!count)\n+\tif (!orig)\n \t\treturn;\n-\t/* allocate an array to help sort the list */\n-\tnodes = xcalloc(count, sizeof(*nodes));\n-\t/* link the list to the array */\n-\tnext_nodes = nodes;\n-\tnext=*list;\n-\twhile (next) {\n-\t\tnext_nodes->list_item = next;\n-\t\tsetter(next->item, next_nodes);\n-\t\tnext_nodes++;\n-\t\tnext = next->next;\n+\t*list = NULL;\n+\n+\t/* Mark them and clear the indegree */\n+\tfor (next = orig; next; next = next->next) {\n+\t\tstruct commit *commit = next->item;\n+\t\tcommit->object.flags |= TOPOSORT;\n+\t\tcommit->indegree = 0;\n \t}\n+\n \t/* update the indegree */\n-\tnext=*list;\n-\twhile (next) {\n+\tfor (next = orig; next; next = next->next) {\n \t\tstruct commit_list * parents = next->item->parents;\n \t\twhile (parents) {\n-\t\t\tstruct commit * parent=parents->item;\n-\t\t\tstruct sort_node * pn = (struct sort_node *) getter(parent);\n+\t\t\tstruct commit *parent = parents->item;\n \n-\t\t\tif (pn)\n-\t\t\t\tpn->indegree++;\n-\t\t\tparents=parents->next;\n+\t\t\tif (parent->object.flags & TOPOSORT)\n+\t\t\t\tparent->indegree++;\n+\t\t\tparents = parents->next;\n \t\t}\n-\t\tnext=next->next;\n \t}\n+\n \t/*\n \t * find the tips\n \t *\n@@ -1220,55 +1173,56 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo,\n \t *\n \t * the tips serve as a starting set for the work queue.\n \t */\n-\tnext=*list;\n+\twork = NULL;\n \tinsert = &work;\n-\twhile (next) {\n-\t\tstruct sort_node * node = (struct sort_node *) getter(next->item);\n+\tfor (next = orig; next; next = next->next) {\n+\t\tstruct commit *commit = next->item;\n \n-\t\tif (node->indegree == 0) {\n-\t\t\tinsert = &commit_list_insert(next->item, insert)->next;\n-\t\t}\n-\t\tnext=next->next;\n+\t\tif (!commit->indegree)\n+\t\t\tinsert = &commit_list_insert(commit, insert)->next;\n \t}\n \n \t/* process the list in topological order */\n \tif (!lifo)\n \t\tsort_by_date(&work);\n+\n+\tpptr = list;\n+\t*list = NULL;\n \twhile (work) {\n-\t\tstruct commit * work_item = pop_commit(&work);\n-\t\tstruct sort_node * work_node = (struct sort_node *) getter(work_item);\n-\t\tstruct commit_list * parents = work_item->parents;\n+\t\tstruct commit *commit;\n+\t\tstruct commit_list *parents, *work_item;\n \n-\t\twhile (parents) {\n-\t\t\tstruct commit * parent=parents->item;\n-\t\t\tstruct sort_node * pn = (struct sort_node *) getter(parent);\n-\n-\t\t\tif (pn) {\n-\t\t\t\t/*\n-\t\t\t\t * parents are only enqueued for emission\n-\t\t\t\t * when all their children have been emitted thereby\n-\t\t\t\t * guaranteeing topological order.\n-\t\t\t\t */\n-\t\t\t\tpn->indegree--;\n-\t\t\t\tif (!pn->indegree) {\n-\t\t\t\t\tif (!lifo)\n-\t\t\t\t\t\tinsert_by_date(parent, &work);\n-\t\t\t\t\telse\n-\t\t\t\t\t\tcommit_list_insert(parent, &work);\n-\t\t\t\t}\n+\t\twork_item = work;\n+\t\twork = work_item->next;\n+\t\twork_item->next = NULL;\n+\n+\t\tcommit = work_item->item;\n+\t\tfor (parents = commit->parents; parents ; parents = parents->next) {\n+\t\t\tstruct commit *parent=parents->item;\n+\n+\t\t\tif (!(parent->object.flags & TOPOSORT))\n+\t\t\t\tcontinue;\n+\n+\t\t\t/*\n+\t\t\t * parents are only enqueued for emission\n+\t\t\t * when all their children have been emitted thereby\n+\t\t\t * guaranteeing topological order.\n+\t\t\t */\n+\t\t\tif (!--parent->indegree) {\n+\t\t\t\tif (!lifo)\n+\t\t\t\t\tinsert_by_date(parent, &work);\n+\t\t\t\telse\n+\t\t\t\t\tcommit_list_insert(parent, &work);\n \t\t\t}\n-\t\t\tparents=parents->next;\n \t\t}\n \t\t/*\n \t\t * work_item is a commit all of whose children\n \t\t * have already been emitted. we can emit it now.\n \t\t */\n-\t\t*pptr = work_node->list_item;\n-\t\tpptr = &(*pptr)->next;\n-\t\t*pptr = NULL;\n-\t\tsetter(work_item, NULL);\n+\t\tcommit->object.flags &= ~TOPOSORT;\n+\t\t*pptr = work_item;\n+\t\tpptr = &work_item->next;\n \t}\n-\tfree(nodes);\n }\n \n /* merge-base stuff */\ndiff --git a/commit.h b/commit.h\nindex b661503..7c71471 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -14,6 +14,7 @@ struct commit_list {\n struct commit {\n \tstruct object object;\n \tvoid *util;\n+\tunsigned int indegree;\n \tunsigned long date;\n \tstruct commit_list *parents;\n \tstruct tree *tree;\n@@ -82,31 +83,12 @@ void clear_commit_marks(struct commit *commit, unsigned int mark);\n /*\n * Performs an in-place topological sort of list supplied.\n *\n- * Pre-conditions for sort_in_topological_order:\n- * all commits in input list and all parents of those\n- * commits must have object.util == NULL\n- *\n- * Pre-conditions for sort_in_topological_order_fn:\n- * all commits in input list and all parents of those\n- * commits must have getter(commit) == NULL\n- *\n- * Post-conditions:\n * invariant of resulting list is:\n * a reachable from b => ord(b) < ord(a)\n * in addition, when lifo == 0, commits on parallel tracks are\n * sorted in the dates order.\n */\n-\n-typedef void (*topo_sort_set_fn_t)(struct commit*, void *data);\n-typedef void* (*topo_sort_get_fn_t)(struct commit*);\n-\n-void topo_sort_default_setter(struct commit *c, void *data);\n-void *topo_sort_default_getter(struct commit *c);\n-\n void sort_in_topological_order(struct commit_list ** list, int lifo);\n-void sort_in_topological_order_fn(struct commit_list ** list, int lifo,\n-\t\t\t\t topo_sort_set_fn_t setter,\n-\t\t\t\t topo_sort_get_fn_t getter);\n \n struct commit_graft {\n \tunsigned char sha1[20];\ndiff --git a/revision.c b/revision.c\nindex e76da0d..e85b4af 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -677,9 +677,6 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \trevs->prune_fn = NULL;\n \trevs->prune_data = NULL;\n \n-\trevs->topo_setter = topo_sort_default_setter;\n-\trevs->topo_getter = topo_sort_default_getter;\n-\n \trevs->commit_format = CMIT_FMT_DEFAULT;\n \n \tdiff_setup(&revs->diffopt);\n@@ -1303,9 +1300,7 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n \tif (revs->topo_order)\n-\t\tsort_in_topological_order_fn(&revs->commits, revs->lifo,\n-\t\t\t\t\t revs->topo_setter,\n-\t\t\t\t\t revs->topo_getter);\n+\t\tsort_in_topological_order(&revs->commits, revs->lifo);\n \treturn 0;\n }\n \ndiff --git a/revision.h b/revision.h\nindex 98a0a8f..1f64576 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -10,6 +10,7 @@\n #define CHILD_SHOWN\t(1u<<6)\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n+#define TOPOSORT\t(1u<<9)\t/* In the active toposort list.. */\n \n struct rev_info;\n struct log_info;\n@@ -96,9 +97,6 @@ struct rev_info {\n \tstruct diff_options diffopt;\n \tstruct diff_options pruning;\n \n-\ttopo_sort_set_fn_t topo_setter;\n-\ttopo_sort_get_fn_t topo_getter;\n-\n \tstruct reflog_walk_info *reflog_info;\n };\n \n"},{"id":"58037","messageId":"alpine.LFD.0.999.0711021333050.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711021301200.3342@woody.linux-foundation.org","subject":"[PATCH 2/2] Support \"history replay\" for git log commands","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-02T20:35:17Z","receivedAt":"2007-11-02T20:35:17Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis notices if we aren't in topological order, and replays the history. \nThus avoiding the need to sort history up front.\n \nSigned-off-by: Linus Torvalds \n---\n\nSee the code and the more complete explanations in [PATCH 0/2]. In \nparticular, see the last section there about the downsides of this: the \n50x expansion of output on the kernel is unacceptable, but if somebody can \nmake a graphical viewer that can react correctly to the \"Replay\" thing, \nI'm sure I can make the replays themselves happen much more rarely.\n\n builtin-blame.c | 2 +-\n builtin-log.c | 35 +++++++++++++++++++++++++++++++++++\n log-tree.c | 10 +++++++---\n revision.c | 29 ++++++++++++++++++++++-------\n revision.h | 6 +++++-\n 5 files changed, 70 insertions(+), 12 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex 8432b82..7b6af8c 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -1502,7 +1502,7 @@ static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt)\n \t\telse {\n \t\t\tcommit->object.flags |= UNINTERESTING;\n \t\t\tif (commit->object.parsed)\n-\t\t\t\tmark_parents_uninteresting(commit);\n+\t\t\t\tmark_parents_uninteresting(revs, commit);\n \t\t}\n \t\t/* treat root commit as boundary */\n \t\tif (!commit->parents && !show_root)\ndiff --git a/builtin-log.c b/builtin-log.c\nindex e8b982d..10e0821 100644\n--- a/builtin-log.c\n+++ b/builtin-log.c\n@@ -77,6 +77,35 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,\n \t}\n }\n \n+static void replay_history(struct rev_info *revs)\n+{\n+\tstruct commit_list *entry;\n+\n+\trevs->trigger_replay = 0;\n+\twhile ((entry = revs->shown) != NULL) {\n+\t\tstruct commit *commit = entry->item;\n+\t\tunsigned flags = commit->object.flags;\n+\n+\t\t/* Undo the SHOWN and FORCE_REPLAY bits */\n+\t\tcommit->object.flags = flags & ~(SHOWN | FORCE_REPLAY);\n+\t\tcommit->indegree = 0;\n+\n+\t\t/* Remove it from the shown list, put it on the commit list */\n+\t\trevs->shown = entry->next;\n+\t\tentry->next = revs->commits;\n+\t\trevs->commits = entry;\n+\n+\t\tprintf(\"Replay %s\\n\", sha1_to_hex(commit->object.sha1));\n+\n+\t\t/* Was this the one that caused us to replay? */\n+\t\tif (flags & FORCE_REPLAY)\n+\t\t\tbreak;\n+\t}\n+\n+\t/* Ok, sort the list to be replayed properly now.. */\n+\tsort_in_topological_order(&revs->commits, revs->lifo);\n+}\n+\n static int cmd_log_walk(struct rev_info *rev)\n {\n \tstruct commit *commit;\n@@ -84,6 +113,12 @@ static int cmd_log_walk(struct rev_info *rev)\n \tprepare_revision_walk(rev);\n \twhile ((commit = get_revision(rev)) != NULL) {\n \t\tlog_tree_commit(rev, commit);\n+\n+\t\tif (rev->replay_history) {\n+\t\t\tif (rev->trigger_replay)\n+\t\t\t\treplay_history(rev);\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!rev->reflog_info) {\n \t\t\t/* we allow cycles in reflog ancestry */\n \t\t\tfree(commit->buffer);\ndiff --git a/log-tree.c b/log-tree.c\nindex 3763ce9..ce9b887 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -6,12 +6,16 @@\n \n struct decoration name_decoration = { \"object names\" };\n \n-static void show_parents(struct commit *commit, int abbrev)\n+static void show_parents(struct rev_info *opt, struct commit *commit, int abbrev)\n {\n \tstruct commit_list *p;\n \tfor (p = commit->parents; p ; p = p->next) {\n \t\tstruct commit *parent = p->item;\n \t\tprintf(\" %s\", diff_unique_abbrev(parent->object.sha1, abbrev));\n+\t\tif (parent->object.flags & SHOWN) {\n+\t\t\topt->trigger_replay = 1;\n+\t\t\tparent->object.flags |= FORCE_REPLAY;\n+\t\t}\n \t}\n }\n \n@@ -147,7 +151,7 @@ void show_log(struct rev_info *opt, const char *sep)\n \t\t}\n \t\tfputs(diff_unique_abbrev(commit->object.sha1, abbrev_commit), stdout);\n \t\tif (opt->parents)\n-\t\t\tshow_parents(commit, abbrev_commit);\n+\t\t\tshow_parents(opt, commit, abbrev_commit);\n \t\tshow_decorations(commit);\n \t\tputchar(opt->diffopt.line_termination);\n \t\treturn;\n@@ -248,7 +252,7 @@ void show_log(struct rev_info *opt, const char *sep)\n \t\tfputs(diff_unique_abbrev(commit->object.sha1, abbrev_commit),\n \t\t stdout);\n \t\tif (opt->parents)\n-\t\t\tshow_parents(commit, abbrev_commit);\n+\t\t\tshow_parents(opt, commit, abbrev_commit);\n \t\tif (parent)\n \t\t\tprintf(\" (from %s)\",\n \t\t\t diff_unique_abbrev(parent->object.sha1,\ndiff --git a/revision.c b/revision.c\nindex e85b4af..e40bc1c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -79,7 +79,7 @@ void mark_tree_uninteresting(struct tree *tree)\n \ttree->buffer = NULL;\n }\n \n-void mark_parents_uninteresting(struct commit *commit)\n+void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_list *parents = commit->parents;\n \n@@ -87,6 +87,10 @@ void mark_parents_uninteresting(struct commit *commit)\n \t\tstruct commit *commit = parents->item;\n \t\tif (!(commit->object.flags & UNINTERESTING)) {\n \t\t\tcommit->object.flags |= UNINTERESTING;\n+\t\t\tif (commit->object.flags & SHOWN) {\n+\t\t\t\trevs->trigger_replay = 1;\n+\t\t\t\tcommit->object.flags |= FORCE_REPLAY;\n+\t\t\t}\n \n \t\t\t/*\n \t\t\t * Normally we haven't parsed the parent\n@@ -97,7 +101,7 @@ void mark_parents_uninteresting(struct commit *commit)\n \t\t\t * to mark its parents recursively too..\n \t\t\t */\n \t\t\tif (commit->parents)\n-\t\t\t\tmark_parents_uninteresting(commit);\n+\t\t\t\tmark_parents_uninteresting(revs, commit);\n \t\t}\n \n \t\t/*\n@@ -167,8 +171,9 @@ static struct commit *handle_commit(struct rev_info *revs, struct object *object\n \t\t\tdie(\"unable to parse commit %s\", name);\n \t\tif (flags & UNINTERESTING) {\n \t\t\tcommit->object.flags |= UNINTERESTING;\n-\t\t\tmark_parents_uninteresting(commit);\n-\t\t\trevs->limited = 1;\n+\t\t\tmark_parents_uninteresting(revs, commit);\n+\t\t\tif (!revs->replay_history)\n+\t\t\t\trevs->limited = 1;\n \t\t}\n \t\treturn commit;\n \t}\n@@ -399,7 +404,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, str\n \t\t\t\treturn -1;\n \t\t\tp->object.flags |= UNINTERESTING;\n \t\t\tif (p->parents)\n-\t\t\t\tmark_parents_uninteresting(p);\n+\t\t\t\tmark_parents_uninteresting(revs, p);\n \t\t\tif (p->object.flags & SEEN)\n \t\t\t\tcontinue;\n \t\t\tp->object.flags |= SEEN;\n@@ -542,7 +547,7 @@ static int limit_list(struct rev_info *revs)\n \t\tif (add_parents_to_list(revs, commit, &list) < 0)\n \t\t\treturn -1;\n \t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n+\t\t\tmark_parents_uninteresting(revs, commit);\n \t\t\tif (everybody_uninteresting(list))\n \t\t\t\tbreak;\n \t\t\tcontinue;\n@@ -995,6 +1000,10 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \t\t\t\trevs->parents = 1;\n \t\t\t\tcontinue;\n \t\t\t}\n+\t\t\tif (!strcmp(arg, \"--replay\")) {\n+\t\t\t\trevs->replay_history = 1;\n+\t\t\t\tcontinue;\n+\t\t\t}\n \t\t\tif (!strcmp(arg, \"--dense\")) {\n \t\t\t\trevs->dense = 1;\n \t\t\t\tcontinue;\n@@ -1386,7 +1395,13 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\tstruct commit *commit = entry->item;\n \n \t\trevs->commits = entry->next;\n-\t\tfree(entry);\n+\n+\t\t/* Are we going to potentially replay? */\n+\t\tif (revs->replay_history) {\n+\t\t\tentry->next = revs->shown;\n+\t\t\trevs->shown = entry;\n+\t\t} else\n+\t\t\tfree(entry);\n \n \t\tif (revs->reflog_info)\n \t\t\tfake_reflog_parent(revs->reflog_info, commit);\ndiff --git a/revision.h b/revision.h\nindex 1f64576..75b320d 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -11,6 +11,7 @@\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n #define TOPOSORT\t(1u<<9)\t/* In the active toposort list.. */\n+#define FORCE_REPLAY\t(1u<<10)\t/* This commit was wrong somehow */\n \n struct rev_info;\n struct log_info;\n@@ -20,6 +21,7 @@ typedef void (prune_fn_t)(struct rev_info *revs, struct commit *commit);\n struct rev_info {\n \t/* Starting list */\n \tstruct commit_list *commits;\n+\tstruct commit_list *shown;\n \tstruct object_array pending;\n \n \t/* Parents of shown commits */\n@@ -36,6 +38,8 @@ struct rev_info {\n \t\t\tno_walk:1,\n \t\t\tremove_empty_trees:1,\n \t\t\tsimplify_history:1,\n+\t\t\treplay_history:1,\n+\t\t\ttrigger_replay:1,\n \t\t\tlifo:1,\n \t\t\ttopo_order:1,\n \t\t\ttag_objects:1,\n@@ -113,7 +117,7 @@ extern int handle_revision_arg(const char *arg, struct rev_info *revs,int flags,\n extern int prepare_revision_walk(struct rev_info *revs);\n extern struct commit *get_revision(struct rev_info *revs);\n \n-extern void mark_parents_uninteresting(struct commit *commit);\n+extern void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit);\n extern void mark_tree_uninteresting(struct tree *tree);\n \n struct name_path {\n"},{"id":"58039","messageId":"7v4pg41hq0.fsf@gitster.siamese.dyndns.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711021333050.3342@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Support \"history replay\" for git log commands","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-02T21:05:11Z","receivedAt":"2007-11-02T21:05:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> This notices if we aren't in topological order, and replays the history. \n> Thus avoiding the need to sort history up front.\n> \n> Signed-off-by: Linus Torvalds \n> ---\n>\n> See the code and the more complete explanations in [PATCH 0/2]. In \n> particular, see the last section there about the downsides of this: the \n> 50x expansion of output on the kernel is unacceptable, but if somebody can \n> make a graphical viewer that can react correctly to the \"Replay\" thing, \n> I'm sure I can make the replays themselves happen much more rarely.\n>\n> builtin-blame.c | 2 +-\n> builtin-log.c | 35 +++++++++++++++++++++++++++++++++++\n> log-tree.c | 10 +++++++---\n> revision.c | 29 ++++++++++++++++++++++-------\n> revision.h | 6 +++++-\n> 5 files changed, 70 insertions(+), 12 deletions(-)\n>\n> diff --git a/builtin-blame.c b/builtin-blame.c\n> index 8432b82..7b6af8c 100644\n> --- a/builtin-blame.c\n> +++ b/builtin-blame.c\n> @@ -1502,7 +1502,7 @@ static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt)\n> \t\telse {\n> \t\t\tcommit->object.flags |= UNINTERESTING;\n> \t\t\tif (commit->object.parsed)\n> -\t\t\t\tmark_parents_uninteresting(commit);\n> +\t\t\t\tmark_parents_uninteresting(revs, commit);\n> \t\t}\n> \t\t/* treat root commit as boundary */\n> \t\tif (!commit->parents && !show_root)\n> diff --git a/builtin-log.c b/builtin-log.c\n> index e8b982d..10e0821 100644\n> --- a/builtin-log.c\n> +++ b/builtin-log.c\n> @@ -77,6 +77,35 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,\n> \t}\n> }\n> \n> +static void replay_history(struct rev_info *revs)\n> +{\n> +\tstruct commit_list *entry;\n> +\n> +\trevs->trigger_replay = 0;\n> +\twhile ((entry = revs->shown) != NULL) {\n> +\t\tstruct commit *commit = entry->item;\n> +\t\tunsigned flags = commit->object.flags;\n> +\n> +\t\t/* Undo the SHOWN and FORCE_REPLAY bits */\n> +\t\tcommit->object.flags = flags & ~(SHOWN | FORCE_REPLAY);\n> +\t\tcommit->indegree = 0;\n> +\n> +\t\t/* Remove it from the shown list, put it on the commit list */\n> +\t\trevs->shown = entry->next;\n> +\t\tentry->next = revs->commits;\n> +\t\trevs->commits = entry;\n> +\n> +\t\tprintf(\"Replay %s\\n\", sha1_to_hex(commit->object.sha1));\n> +\n> +\t\t/* Was this the one that caused us to replay? */\n> +\t\tif (flags & FORCE_REPLAY)\n> +\t\t\tbreak;\n\nCan one iteration of loop in log_tree_commit() smudge more\nthan one commits with FORCE_REPLAY? Maybe make the\ntrigger_replay a counter and count down in this loop until we\nfind that many commits that have the FORCE_REPLAY flag?\n"},{"id":"58041","messageId":"alpine.LFD.0.999.0711021416450.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"7v4pg41hq0.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 2/2] Support \"history replay\" for git log commands","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-02T21:17:26Z","receivedAt":"2007-11-02T21:17:26Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 2 Nov 2007, Junio C Hamano wrote:\n> \n> Can one iteration of loop in log_tree_commit() smudge more\n> than one commits with FORCE_REPLAY? Maybe make the\n> trigger_replay a counter and count down in this loop until we\n> find that many commits that have the FORCE_REPLAY flag?\n\nGood point, and yes, that sounds like the right thing to do.\n\n\t\tLinus\n"},{"id":"58062","messageId":"alpine.LFD.0.999.0711021809060.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711021301200.3342@woody.linux-foundation.org","subject":"Re: [PATCH 0/2] History replay support","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-03T01:40:02Z","receivedAt":"2007-11-03T01:40:02Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 2 Nov 2007, Linus Torvalds wrote:\n> \n> The bad news is that it doesn't work well in this simplistic form, because \n> there is a O(n**2) behaviour when replays *do* happen, ie we end up having \n> replays within replays [..]\n\nGaah. the more I look at this, the more I think the topo sort should be \ndone at the visualization side.\n\nIt's really quite cheap to do the topo sort, *and* it's really quite cheap \nto do the tests that trigger the topo sort, but what's expensive is to \nre-output all the data again!\n\nThe silly thing is, I think I've come up with an \"almost optimal\" \nsolution, but it's so ugly that I'm a bit ashamed of it.\n\nThat almost optimal solution is simply:\n - get the first (say: 100) commits, and topo-sort just them. Feed it \n to the visualizer.\n - the visualizer will now have enough to work with in order to show the \n starting screen and set the cursor to the hourglass or whatever the \n \"wait for it\" thing is.\n - get the rest of the commits at our normal leisurely pace (whether it \n is one second of 17).\n - output the total number of commits (so that the visualizer can re-size \n the slider and/or allocate some big array just once), topo-sort it all, \n and output the full thing.\n\nIt's disgusting. But it avoids the unnecessary data transfer - except for \njust the first 100 commits that get sent twice. And it gets what *I* look \nfor, namely that \"immediate\" feel to the initial pop-up of the history.\n\n\t\t\tLinus\n"},{"id":"58079","messageId":"e5bfff550711030056m5f62eb21k4972e1340f7d6e6c@mail.gmail.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711021809060.3342@woody.linux-foundation.org","subject":"Re: [PATCH 0/2] History replay support","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-11-03T07:56:35Z","receivedAt":"2007-11-03T07:56:35Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 11/3/07, Linus Torvalds wrote:\n>\n>\n> On Fri, 2 Nov 2007, Linus Torvalds wrote:\n> >\n> > The bad news is that it doesn't work well in this simplistic form, because\n> > there is a O(n**2) behaviour when replays *do* happen, ie we end up having\n> > replays within replays [..]\n>\n> Gaah. the more I look at this, the more I think the topo sort should be\n> done at the visualization side.\n>\n> It's really quite cheap to do the topo sort, *and* it's really quite cheap\n> to do the tests that trigger the topo sort, but what's expensive is to\n> re-output all the data again!\n>\n> The silly thing is, I think I've come up with an \"almost optimal\"\n> solution, but it's so ugly that I'm a bit ashamed of it.\n>\n> That almost optimal solution is simply:\n> - get the first (say: 100) commits, and topo-sort just them. Feed it\n> to the visualizer.\n> - the visualizer will now have enough to work with in order to show the\n> starting screen and set the cursor to the hourglass or whatever the\n> \"wait for it\" thing is.\n> - get the rest of the commits at our normal leisurely pace (whether it\n> is one second of 17).\n> - output the total number of commits (so that the visualizer can re-size\n> the slider and/or allocate some big array just once), topo-sort it all,\n> and output the full thing.\n>\n> It's disgusting. But it avoids the unnecessary data transfer - except for\n> just the first 100 commits that get sent twice. And it gets what *I* look\n> for, namely that \"immediate\" feel to the initial pop-up of the history.\n>\n\nIt's not disgusting is human perception oriented !\n\nAll this stuff is not needed to get the sha faster, but to let think\nthe user that are faster. It's for strictly human consumption, so I\nwould say your \"ugly\" solution is the best for me.\n\nA bunch of revisions, just to let user eyes to re-focus on new stuff\n(and some hundredths of milliseconds are already elapsed after this)\nwhile in the background the real, shadowed, work goes on.\n\nIt's also easy on the client GUI side, simply discard all and reload\nas soon _correct_ data arrives.\n\nSo the new option could became:\n\ngit log --fast-output 100 500 --topo-order <...whatever...>\n\nwhere git log outputs as soon as it can 100 commits and feeds it to\nthe visualizer. If the _normal_ commits are still not ready after 500\nms are elapsed then git log spits out another 100 commits chunk and so\non at 500ms intervals until good commits are ready. Then outputs the\nfull thing.\n\nIt is very user perception oriented, but hey, so is a GUI!\n\nMarco\n\nP.S: A little optimization for small repositories would be that git\nlog *waits* at maximum 500ms before to output the first 100 commits\nchunk, so that in case of small repos (thousands of revisions) or in\ncase of warmed up cache the commits in output are already the good\nones, no need for fakes!\n"},{"id":"58160","messageId":"alpine.LFD.0.999.0711031103340.3342@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711021809060.3342@woody.linux-foundation.org","subject":"[REPLACEMENT PATCH 2/2] Add \"--early-output\" log flag for interactive GUI use","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-03T18:11:10Z","receivedAt":"2007-11-03T18:11:10Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis adds support for \"--early-output[=n]\" as a flag to the \"git log\"\nfamily of commands. This allows GUI programs to state that they want to\nget some output early, in order to be able to show at least something\nquickly, even if the full output may take longer to generate.\n\nIf no count is specified, a default count of a hundred commits will be\nused, although the actual numbr of commits output may be smaller\ndepending on how many commits were actually found in the first tenth of\na second (or if *everything* was found before that, in which case no\nearly output will be provided, and only the final list is made\navailable).\n\nWhen the full list is generated, there will be a \"Final output:\" string\nprepended to it, regardless of whether any early commits were shown or\nnot, so that the consumer can always know the difference between early\noutput and the final list.\n\nSigned-off-by: Linus Torvalds \n---\n\nThis replaces my 2/2 patch from yesterday, but still relies on the \ntopo-sorting cleanups in 1/2 (which are really totally independent, and \nprobably could go in regardless of any of this series).\n\nInstead of having a generic replay mechanism, this one just does *one* \nreplay, and discards even that if it can generate all the commits really \nquickly.\n\nThe timeout right now is set to a pretty aggressive one-tenth-of-a- \nsecond, and realistically that could/should probably be longer, but making \nit short makes sure that we actually trigger this in normal use, so I \nthink this is the right approach for the initial implementation.\n\nTry it out, with\n\n\tgit log --early-output=2\n\nand look at what happens: if it cannot generate all the commits in the \nfirst 0.1 seconds, it will take what it *could* generate, sort it \ntopologically (you can add \"--date-order\" if you want), and show the first \ntwo commits.\n\nWhen it then generates the rest, it will add a \"Final output:\" line, and \nthen re-generate it all.\n\nThe intent is for a GUI front-end to be able to use the first one-hundred \nor so commits to populate the commit log, and show the window, and not \nhave to worry about the fact that the rest of the data (how-ever many \nhundred thousand commits there are) may take much more time to arrive.\n\nSo not only is this patch pretty straightforward in itself, I think usage \nshould be pretty straightforward too.\n\n builtin-log.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n revision.c | 22 ++++++++++++++++++\n revision.h | 4 +++\n 3 files changed, 93 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin-log.c b/builtin-log.c\nindex e8b982d..707add2 100644\n--- a/builtin-log.c\n+++ b/builtin-log.c\n@@ -77,11 +77,78 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,\n \t}\n }\n \n+static void log_show_early(struct rev_info *revs, struct commit_list *list)\n+{\n+\tint i = revs->early_output;\n+\n+\tsort_in_topological_order(&list, revs->lifo);\n+\twhile (list && i) {\n+\t\tstruct commit *commit = list->item;\n+\t\tlog_tree_commit(revs, commit);\n+\t\tlist = list->next;\n+\t\ti--;\n+\t}\n+}\n+\n+static void early_output(int signal)\n+{\n+\tshow_early_output = log_show_early;\n+}\n+\n+static void setup_early_output(struct rev_info *rev)\n+{\n+\tstruct sigaction sa;\n+\tstruct itimerval v;\n+\n+\t/*\n+\t * Set up the signal handler, minimally intrusively:\n+\t * we only set a single volatile integer word (not\n+\t * using sigatomic_t - trying to avoid unnecessary\n+\t * system dependencies and headers), and using\n+\t * SA_RESTART.\n+\t */\n+\tmemset(&sa, 0, sizeof(sa));\n+\tsa.sa_handler = early_output;\n+\tsigemptyset(&sa.sa_mask);\n+\tsa.sa_flags = SA_RESTART;\n+\tsigaction(SIGALRM, &sa, NULL);\n+\n+\t/*\n+\t * If we can get the whole output in less than a\n+\t * tenth of a second, don't even bother doing the\n+\t * early-output thing..\n+\t *\n+\t * This is a one-time-only trigger.\n+\t */\n+\tmemset(&v, 0, sizeof(v));\n+\tv.it_value.tv_sec = 0;\n+\tv.it_value.tv_usec = 100000;\n+\tsetitimer(ITIMER_REAL, &v, NULL);\n+}\n+\n+static void finish_early_output(struct rev_info *rev)\n+{\n+\tsignal(SIGALRM, SIG_IGN);\n+\tif (rev->shown_one) {\n+\t\trev->shown_one = 0;\n+\t\tif (rev->commit_format != CMIT_FMT_ONELINE)\n+\t\t\tputchar(rev->diffopt.line_termination);\n+\t}\n+\tprintf(\"Final output:\\n\");\n+}\n+\n static int cmd_log_walk(struct rev_info *rev)\n {\n \tstruct commit *commit;\n \n+\tif (rev->early_output)\n+\t\tsetup_early_output(rev);\n+\n \tprepare_revision_walk(rev);\n+\n+\tif (rev->early_output)\n+\t\tfinish_early_output(rev);\n+\n \twhile ((commit = get_revision(rev)) != NULL) {\n \t\tlog_tree_commit(rev, commit);\n \t\tif (!rev->reflog_info) {\ndiff --git a/revision.c b/revision.c\nindex e85b4af..26610bb 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -10,6 +10,8 @@\n #include \"reflog-walk.h\"\n #include \"patch-ids.h\"\n \n+volatile show_early_output_fn_t show_early_output;\n+\n static char *path_name(struct name_path *path, const char *name)\n {\n \tstruct name_path *p;\n@@ -533,6 +535,7 @@ static int limit_list(struct rev_info *revs)\n \t\tstruct commit_list *entry = list;\n \t\tstruct commit *commit = list->item;\n \t\tstruct object *obj = &commit->object;\n+\t\tshow_early_output_fn_t show;\n \n \t\tlist = list->next;\n \t\tfree(entry);\n@@ -550,6 +553,13 @@ static int limit_list(struct rev_info *revs)\n \t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n \t\t\tcontinue;\n \t\tp = &commit_list_insert(commit, p)->next;\n+\n+\t\tshow = show_early_output;\n+\t\tif (!show)\n+\t\t\tcontinue;\n+\n+\t\tshow(revs, newlist);\n+\t\tshow_early_output = NULL;\n \t}\n \tif (revs->cherry_pick)\n \t\tcherry_pick_list(newlist, revs);\n@@ -991,6 +1001,18 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \t\t\t\trevs->topo_order = 1;\n \t\t\t\tcontinue;\n \t\t\t}\n+\t\t\tif (!prefixcmp(arg, \"--early-output\")) {\n+\t\t\t\tint count = 100;\n+\t\t\t\tswitch (arg[14]) {\n+\t\t\t\tcase '=':\n+\t\t\t\t\tcount = atoi(arg+15);\n+\t\t\t\t\t/* Fallthrough */\n+\t\t\t\tcase 0:\n+\t\t\t\t\trevs->topo_order = 1;\n+\t\t\t\t\trevs->early_output = count;\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t}\n \t\t\tif (!strcmp(arg, \"--parents\")) {\n \t\t\t\trevs->parents = 1;\n \t\t\t\tcontinue;\ndiff --git a/revision.h b/revision.h\nindex 1f64576..d8a5a50 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -30,6 +30,8 @@ struct rev_info {\n \tvoid *prune_data;\n \tprune_fn_t *prune_fn;\n \n+\tunsigned int early_output;\n+\n \t/* Traversal flags */\n \tunsigned int\tdense:1,\n \t\t\tno_merges:1,\n@@ -105,6 +107,8 @@ struct rev_info {\n #define REV_TREE_DIFFERENT\t2\n \n /* revision.c */\n+typedef void (*show_early_output_fn_t)(struct rev_info *, struct commit_list *);\n+volatile show_early_output_fn_t show_early_output;\n \n extern void init_revisions(struct rev_info *revs, const char *prefix);\n extern int setup_revisions(int argc, const char **argv, struct rev_info *revs, const char *def);\n"},{"id":"58169","messageId":"e5bfff550711031252g448fd886s2bd3903318829e2b@mail.gmail.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711031103340.3342@woody.linux-foundation.org","subject":"Re: [REPLACEMENT PATCH 2/2] Add \"--early-output\" log flag for interactive GUI use","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-11-03T19:52:40Z","receivedAt":"2007-11-03T19:52:40Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 11/3/07, Linus Torvalds wrote:\n>\n>\n> Try it out, with\n>\n> git log --early-output=2\n>\n> and look at what happens\n\nIt works for me! tomorrow I will try to teach qgit to play with this new toy.\n\nBTW there are some warning around that disappear adding\n\nextern void sort_in_topological_order(struct commit_list ** list, int lifo);\n\nsomewhere in commit.h\n\nMarco\n"},{"id":"58192","messageId":"18221.4866.623031.306945@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711021809060.3342@woody.linux-foundation.org","subject":"Re: [PATCH 0/2] History replay support","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-11-04T00:32:02Z","receivedAt":"2007-11-04T00:32:02Z","isPatch":true,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> It's disgusting. But it avoids the unnecessary data transfer - except for \n> just the first 100 commits that get sent twice. And it gets what *I* look \n> for, namely that \"immediate\" feel to the initial pop-up of the history.\n\nYes. And it avoids the need for gitk to have to do any re-ordering of\nthe commits that it gets from git log. In the case where the first\ncommits come out in a different order in the final list, gitk can just\ntruncate its list at the point of difference and re-read from there,\nwhich is a lot less time-consuming than having to make a decision\nfor every commit about where it should go in the list.\n\nI have actually been trying to come up with a decent way to generate\nthe list incrementally without using --topo-order for months now. One\nof the problems is that while Tcl can append things to the end of a\nlong list efficiently, and can index long lists efficiently, inserting\nthings into the middle of a long list is slow. That makes any\ninsertion-sort type of algorithm unbearably slow. And it's not just\nwhen we get parents before children that I have to insert into the\nmiddle of the list -- reordering a date-order list into one where we\nsee the string of commits that were merged immediately after a merge\ncommit requires a lot of insertions.\n\nI do have an approach that I'm thinking about that builds up the list\nas a series of \"arcs\", each of which is a string of commits with\nexactly one parent and one child. Each new commit from git log\n(without --topo-order) then either gets appended to an arc (there can\nbe several arcs that are still growing at any given point), or it is a\nmerge or a branch point, which means it terminates some arc(s) and/or\nstarts new arc(s). The final list of commits is then composed by\nconcatenating the arcs in a suitable order. That avoids doing\ninsertions but does make things more complex for the consumers of the\nlist (the layout algorithm and the search function), and it\npotentially makes it much slower to go from a row number to the commit\ndisplayed on that row.\n\nHowever, for now I think that using --early-output is a good\ncompromise solution that makes the startup much faster (or at least\n*appear* to be much faster :) without adding much complexity.\n\nRegards,\nPaul.\n"},{"id":"58201","messageId":"18221.14113.498416.396006@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711031103340.3342@woody.linux-foundation.org","subject":"Re: [REPLACEMENT PATCH 2/2] Add \"--early-output\" log flag for interactive GUI use","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-11-04T03:06:09Z","receivedAt":"2007-11-04T03:06:09Z","isPatch":true,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> When the full list is generated, there will be a \"Final output:\" string\n> prepended to it, regardless of whether any early commits were shown or\n> not, so that the consumer can always know the difference between early\n> output and the final list.\n\nHow hard would it be to put the total number of commits on that \"Final\noutput\" line? That would be useful for me.\n\nPaul.\n"},{"id":"58216","messageId":"alpine.LFD.0.999.0711032234030.15101@woody.linux-foundation.org","threadId":"10493","inReplyTo":"18221.14113.498416.396006@cargo.ozlabs.ibm.com","subject":"Re: [REPLACEMENT PATCH 2/2] Add \"--early-output\" log flag for interactive GUI use","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-04T05:38:18Z","receivedAt":"2007-11-04T05:38:18Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 4 Nov 2007, Paul Mackerras wrote:\n>\n> Linus Torvalds writes:\n> \n> > When the full list is generated, there will be a \"Final output:\" string\n> > prepended to it, regardless of whether any early commits were shown or\n> > not, so that the consumer can always know the difference between early\n> > output and the final list.\n> \n> How hard would it be to put the total number of commits on that \"Final\n> output\" line? That would be useful for me.\n\nNot hard. I think we basically have it anyway. The reason I didn't do it \nis that there's actually multiple numbers: there's the number of primary \n(\"interesting\") commits, and then there are the \"others\", ie the edge \nthings etc. So the number I'd pick would be the number of actual \ninteresting commits, no edges, no nothing. Or what?\n\nOne other thing I was thinking of was also to perhaps allow multiple \npartial early-output things, in case we get just 5 commits in the first \n0.1 seconds, then 50 in the first second, and 200 after 2 seconds.. I can \nwell imagine getting the full list taking a long time over a network \nfilesystem (somebody mentioned samba), and maybe having just a single \ntrigger is too inflexible.\n\n\t\t\tLinus\n"},{"id":"58221","messageId":"18221.28744.805398.598809@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711032234030.15101@woody.linux-foundation.org","subject":"Re: [REPLACEMENT PATCH 2/2] Add \"--early-output\" log flag for interactive GUI use","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-11-04T07:10:00Z","receivedAt":"2007-11-04T07:10:00Z","isPatch":true,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> > How hard would it be to put the total number of commits on that \"Final\n> > output\" line? That would be useful for me.\n> \n> Not hard. I think we basically have it anyway. The reason I didn't do it \n> is that there's actually multiple numbers: there's the number of primary \n> (\"interesting\") commits, and then there are the \"others\", ie the edge \n> things etc. So the number I'd pick would be the number of actual \n> interesting commits, no edges, no nothing. Or what?\n\nAny of those numbers is probably good enough for a progress bar, but\nideally it would be the total number that you are going to output.\nSo, with --boundary it would include the edge commits, otherwise it\nwould just be the interesting commits, I think.\n\n> One other thing I was thinking of was also to perhaps allow multiple \n> partial early-output things, in case we get just 5 commits in the first \n> 0.1 seconds, then 50 in the first second, and 200 after 2 seconds.. I can \n> well imagine getting the full list taking a long time over a network \n> filesystem (somebody mentioned samba), and maybe having just a single \n> trigger is too inflexible.\n\nIn fact gitk won't mind if you give it multiple occurrences of \"Final\noutput\", as long as you start from the beginning again after each\noccurrence. So having multiple triggers is certainly doable as far as\ngitk is concerned. Later on we could optimize that by having git log\nmatch up how many initial commits are the same in both the new list\nand the old list, and have it output that rather than the N commits\nthat were the same as last time.\n\nPaul.\n"},{"id":"58224","messageId":"e5bfff550711040052y486d71edu81bcddc8919dd496@mail.gmail.com","threadId":"10493","inReplyTo":"18221.28744.805398.598809@cargo.ozlabs.ibm.com","subject":"Re: [REPLACEMENT PATCH 2/2] Add \"--early-output\" log flag for interactive GUI use","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-11-04T07:52:58Z","receivedAt":"2007-11-04T07:52:58Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 11/4/07, Paul Mackerras wrote:\n>\n> Later on we could optimize that by having git log\n> match up how many initial commits are the same in both the new list\n> and the old list, and have it output that rather than the N commits\n> that were the same as last time.\n>\n\nPartial output of commits after \"Final output\" line would be more\ndifficult for me to handle instead or restarting form beginning.\n\nOne possible optimization along this line instead would be that git\nlog match up how many initial commits are the same in both the new\nlist and the old list, and if the old list is whole included\nunmodifies in the new simply git log outputs the new commits (not\nalready present in the old) without the \"Final output\" line.\n\nMarco\n"},{"id":"58287","messageId":"alpine.LFD.0.999.0711041004220.15101@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711032234030.15101@woody.linux-foundation.org","subject":"Re: [REPLACEMENT PATCH 2/2] Add \"--early-output\" log flag for interactive GUI use","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-04T18:11:54Z","receivedAt":"2007-11-04T18:11:54Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 3 Nov 2007, Linus Torvalds wrote:\n> > \n> > How hard would it be to put the total number of commits on that \"Final\n> > output\" line? That would be useful for me.\n> \n> Not hard. I think we basically have it anyway.\n\nActually, I take that back.\n\nIt's hard. Not because we don't have the commits, but because while we do \nthe top-level shape pruning in the eearly stages, we do *not* do the final \npath-limiting until we actually output the commits.\n\nWhich actually makes \"--early-output\" right now do some rather odd things \nwhen you use a path limiter: we don't do the \"rewrite_parents()\" thing \nuntil later, so the early output will have done the first level of history \nsimplification, but it won't have made history *dense* yet.\n\nI'm looking at it now, I'll have to think about this a bit more. It might \nbe trivial to fix, but this thing has real potential for being subtle.\n\n\t\t\tLinus\n"},{"id":"58301","messageId":"alpine.LFD.0.999.0711041124050.15101@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711041004220.15101@woody.linux-foundation.org","subject":"[PATCH 3/2] Enhance --early-output format","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-04T20:12:05Z","receivedAt":"2007-11-04T20:12:05Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis makes --early-output a bit more advanced, and actually makes it \ngenerate multiple \"Final output:\" headers as it updates things \nasynchronously. I realize that the \"Final output:\" line is now illogical, \nsince it's not really final until it also says \"done\", but \n\nIt now _always_ generates a \"Final output:\" header in front of any commit \nlist, and that output header gives you a *guess* at the maximum number of \ncommits available. However, it should be noted that the guess can be \ncompletely off: I do a reasonable job estimating it, but it is not meant \nto be exact. \n\nSo what happens is that you may get output like this:\n\n - at 0.1 seconds:\n\n\tFinal output: 2 incomplete\n\t.. 2 commits listed ..\n\n - half a second later:\n\n\tFinal output: 33 incomplete\n\t.. 33 commits listed ..\n\n - another half a second after that:\t\n\n\tFinal output: 71 incomplete\n\t.. 71 commits listed ..\n\n - another half second later:\n\n\tFinal output: 136 incomplete\n\t.. 100 commits listed: we hit the --early-output limit, and\n\t.. will only output 100 commits, and after this you'll not\n\t.. see an \"incomplete\" report any more since you got as much\n\t.. early output as you asked for!\n\n - .. and then finally:\n\n\tFinal output: 73106 done\n\t.. all the commits ..\n\nThe above is a real-life scenario on my current kernel tree after having \nflushed all the caches.\n\nTested with the experimental gitk patch that Paul sent out, and by looking \nat the actual log output (and verifying that my commit count guesses \nactually match real life fairly well).\n\nSigned-off-by: Linus Torvalds \n---\n\nOn Sun, 4 Nov 2007, Linus Torvalds wrote:\n> \n> I'm looking at it now, I'll have to think about this a bit more. It might \n> be trivial to fix, but this thing has real potential for being subtle.\n\nIt wasn't totally trivial, but it doesn't seem to be excessively subtle \neither. About half the patch is moving around some code to look at whether \nthe commit is interesting or not and rewriting the parents, so that it can \nbe shared with the revision walker.\n\n builtin-log.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++--------\n revision.c | 63 +++++++++++++++++++++++-----------------\n revision.h | 8 +++++\n 3 files changed, 119 insertions(+), 40 deletions(-)\n\ndiff --git a/builtin-log.c b/builtin-log.c\nindex 707add2..268a7af 100644\n--- a/builtin-log.c\n+++ b/builtin-log.c\n@@ -77,17 +77,85 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,\n \t}\n }\n \n+/*\n+ * This gives a rough estimate for how many commits we\n+ * will print out in the list.\n+ */\n+static int estimate_commit_count(struct rev_info *rev, struct commit_list *list)\n+{\n+\tint n = 0;\n+\n+\twhile (list) {\n+\t\tstruct commit *commit = list->item;\n+\t\tunsigned int flags = commit->object.flags;\n+\n+\t\tlist = list->next;\n+\t\tif (flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\tif (rev->prune_fn && rev->dense && !(flags & TREECHANGE)) {\n+\t\t\tif (commit->parents && !commit->parents->next)\n+\t\t\t\tcontinue;\n+\t\t}\n+\t\tn++;\n+\t}\n+\treturn n;\n+}\n+\n+static void show_early_header(struct rev_info *rev, const char *stage, int nr)\n+{\n+\tif (rev->shown_one) {\n+\t\trev->shown_one = 0;\n+\t\tif (rev->commit_format != CMIT_FMT_ONELINE)\n+\t\t\tputchar(rev->diffopt.line_termination);\n+\t}\n+\tprintf(\"Final output: %d %s\\n\", nr, stage);\n+}\n+\n+struct itimerval early_output_timer;\n+\n static void log_show_early(struct rev_info *revs, struct commit_list *list)\n {\n \tint i = revs->early_output;\n+\tint show_header = 1;\n \n \tsort_in_topological_order(&list, revs->lifo);\n \twhile (list && i) {\n \t\tstruct commit *commit = list->item;\n-\t\tlog_tree_commit(revs, commit);\n+\t\tswitch (simplify_commit(revs, commit)) {\n+\t\tcase commit_show:\n+\t\t\tif (show_header) {\n+\t\t\t\tint n = estimate_commit_count(revs, list);\n+\t\t\t\tshow_early_header(revs, \"incomplete\", n);\n+\t\t\t\tshow_header = 0;\n+\t\t\t}\n+\t\t\tlog_tree_commit(revs, commit);\n+\t\t\ti--;\n+\t\t\tbreak;\n+\t\tcase commit_ignore:\n+\t\t\tbreak;\n+\t\tcase commit_error:\n+\t\t\treturn;\n+\t\t}\n \t\tlist = list->next;\n-\t\ti--;\n \t}\n+\n+\t/* Did we already get enough commits for the early output? */\n+\tif (!i)\n+\t\treturn;\n+\n+\t/*\n+\t * ..if no, then repeat it twice a second until we\n+\t * do.\n+\t *\n+\t * NOTE! We don't use \"it_interval\", because if the\n+\t * reader isn't listening, we want our output to be\n+\t * throttled by the writing, and not have the timer\n+\t * trigger every second even if we're blocked on a\n+\t * reader!\n+\t */\n+\tearly_output_timer.it_value.tv_sec = 0;\n+\tearly_output_timer.it_value.tv_usec = 500000;\n+\tsetitimer(ITIMER_REAL, &early_output_timer, NULL);\n }\n \n static void early_output(int signal)\n@@ -98,7 +166,6 @@ static void early_output(int signal)\n static void setup_early_output(struct rev_info *rev)\n {\n \tstruct sigaction sa;\n-\tstruct itimerval v;\n \n \t/*\n \t * Set up the signal handler, minimally intrusively:\n@@ -120,21 +187,16 @@ static void setup_early_output(struct rev_info *rev)\n \t *\n \t * This is a one-time-only trigger.\n \t */\n-\tmemset(&v, 0, sizeof(v));\n-\tv.it_value.tv_sec = 0;\n-\tv.it_value.tv_usec = 100000;\n-\tsetitimer(ITIMER_REAL, &v, NULL);\n+\tearly_output_timer.it_value.tv_sec = 0;\n+\tearly_output_timer.it_value.tv_usec = 100000;\n+\tsetitimer(ITIMER_REAL, &early_output_timer, NULL);\n }\n \n static void finish_early_output(struct rev_info *rev)\n {\n+\tint n = estimate_commit_count(rev, rev->commits);\n \tsignal(SIGALRM, SIG_IGN);\n-\tif (rev->shown_one) {\n-\t\trev->shown_one = 0;\n-\t\tif (rev->commit_format != CMIT_FMT_ONELINE)\n-\t\t\tputchar(rev->diffopt.line_termination);\n-\t}\n-\tprintf(\"Final output:\\n\");\n+\tshow_early_header(rev, \"done\", n);\n }\n \n static int cmd_log_walk(struct rev_info *rev)\ndiff --git a/revision.c b/revision.c\nindex 26610bb..5d6f208 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1398,6 +1398,36 @@ static int commit_match(struct commit *commit, struct rev_info *opt)\n \t\t\t commit->buffer, strlen(commit->buffer));\n }\n \n+enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)\n+{\n+\tif (commit->object.flags & SHOWN)\n+\t\treturn commit_ignore;\n+\tif (revs->unpacked && has_sha1_pack(commit->object.sha1, revs->ignore_packed))\n+\t\treturn commit_ignore;\n+\tif (commit->object.flags & UNINTERESTING)\n+\t\treturn commit_ignore;\n+\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n+\t\treturn commit_ignore;\n+\tif (revs->no_merges && commit->parents && commit->parents->next)\n+\t\treturn commit_ignore;\n+\tif (!commit_match(commit, revs))\n+\t\treturn commit_ignore;\n+\tif (revs->prune_fn && revs->dense) {\n+\t\t/* Commit without changes? */\n+\t\tif (!(commit->object.flags & TREECHANGE)) {\n+\t\t\t/* drop merges unless we want parenthood */\n+\t\t\tif (!revs->parents)\n+\t\t\t\treturn commit_ignore;\n+\t\t\t/* non-merge - always ignore it */\n+\t\t\tif (!commit->parents || !commit->parents->next)\n+\t\t\t\treturn commit_ignore;\n+\t\t}\n+\t\tif (revs->parents && rewrite_parents(revs, commit) < 0)\n+\t\t\treturn commit_error;\n+\t}\n+\treturn commit_show;\n+}\n+\n static struct commit *get_revision_1(struct rev_info *revs)\n {\n \tif (!revs->commits)\n@@ -1425,36 +1455,15 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (add_parents_to_list(revs, commit, &revs->commits) < 0)\n \t\t\t\treturn NULL;\n \t\t}\n-\t\tif (commit->object.flags & SHOWN)\n-\t\t\tcontinue;\n-\n-\t\tif (revs->unpacked && has_sha1_pack(commit->object.sha1,\n-\t\t\t\t\t\t revs->ignore_packed))\n-\t\t continue;\n \n-\t\tif (commit->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n-\t\t\tcontinue;\n-\t\tif (revs->no_merges &&\n-\t\t commit->parents && commit->parents->next)\n-\t\t\tcontinue;\n-\t\tif (!commit_match(commit, revs))\n+\t\tswitch (simplify_commit(revs, commit)) {\n+\t\tcase commit_ignore:\n \t\t\tcontinue;\n-\t\tif (revs->prune_fn && revs->dense) {\n-\t\t\t/* Commit without changes? */\n-\t\t\tif (!(commit->object.flags & TREECHANGE)) {\n-\t\t\t\t/* drop merges unless we want parenthood */\n-\t\t\t\tif (!revs->parents)\n-\t\t\t\t\tcontinue;\n-\t\t\t\t/* non-merge - always ignore it */\n-\t\t\t\tif (!commit->parents || !commit->parents->next)\n-\t\t\t\t\tcontinue;\n-\t\t\t}\n-\t\t\tif (revs->parents && rewrite_parents(revs, commit) < 0)\n-\t\t\t\treturn NULL;\n+\t\tcase commit_error:\n+\t\t\treturn -1;\n+\t\tdefault:\n+\t\t\treturn commit;\n \t\t}\n-\t\treturn commit;\n \t} while (revs->commits);\n \treturn NULL;\n }\ndiff --git a/revision.h b/revision.h\nindex d8a5a50..2232247 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -133,4 +133,12 @@ extern void add_object(struct object *obj,\n \n extern void add_pending_object(struct rev_info *revs, struct object *obj, const char *name);\n \n+enum commit_action {\n+\tcommit_ignore,\n+\tcommit_show,\n+\tcommit_error\n+};\n+\n+extern enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit);\n+\n #endif\n"},{"id":"58411","messageId":"7vsl3kphjp.fsf@gitster.siamese.dyndns.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711041124050.15101@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Enhance --early-output format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-05T20:24:10Z","receivedAt":"2007-11-05T20:24:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> It wasn't totally trivial, but it doesn't seem to be excessively subtle \n> either. About half the patch is moving around some code to look at whether \n> the commit is interesting or not and rewriting the parents, so that it can \n> be shared with the revision walker.\n\nVery nicely done.\n\n> +\twhile (list) {\n> +\t\tstruct commit *commit = list->item;\n> +\t\tunsigned int flags = commit->object.flags;\n> +\n> +\t\tlist = list->next;\n> +\t\tif (flags & UNINTERESTING)\n> +\t\t\tcontinue;\n> +\t\tif (rev->prune_fn && rev->dense && !(flags & TREECHANGE)) {\n> +\t\t\tif (commit->parents && !commit->parents->next)\n> +\t\t\t\tcontinue;\n> +\t\t}\n\nWhen looking at:\n\n\tif (A && B && C) {\n \tif (D && E)\n \tcontinue;\n\t}\n\nan uninitiated might say \"Huh? Why use nested 'if'?\", but to\nsomebody who knows how revision traversal works, the above split\nis a more logical way to test this condition. Maybe one liner\ncomment is in order?\n\n> +static void show_early_header(struct rev_info *rev, const char *stage, int nr)\n> +{\n> +\tif (rev->shown_one) {\n> +\t\trev->shown_one = 0;\n> +\t\tif (rev->commit_format != CMIT_FMT_ONELINE)\n> +\t\t\tputchar(rev->diffopt.line_termination);\n> +\t}\n> +\tprintf(\"Final output: %d %s\\n\", nr, stage);\n> +}\n\nAs you noted, this is more like \"Partial output\" now.\nHow about painting the bikeshed pink by saying:\n\n\tPartial output: 20\n Partial output: 70\n Final output: 70000\n\n> +\t/* Did we already get enough commits for the early output? */\n> +\tif (!i)\n> +\t\treturn;\n> +\n> +\t/*\n> +\t * ..if no, then repeat it twice a second until we\n> +\t * do.\n> +\t *\n> +\t * NOTE! We don't use \"it_interval\", because if the\n> +\t * reader isn't listening, we want our output to be\n> +\t * throttled by the writing, and not have the timer\n> +\t * trigger every second even if we're blocked on a\n> +\t * reader!\n> +\t */\n\nA comment like this is very much appreciated.\n\n> +\tearly_output_timer.it_value.tv_sec = 0;\n> +\tearly_output_timer.it_value.tv_usec = 500000;\n> +\tsetitimer(ITIMER_REAL, &early_output_timer, NULL);\n> }\n"},{"id":"58413","messageId":"alpine.LFD.0.999.0711051233270.15101@woody.linux-foundation.org","threadId":"10493","inReplyTo":"7vsl3kphjp.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 3/2] Enhance --early-output format","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-05T20:47:31Z","receivedAt":"2007-11-05T20:47:31Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 5 Nov 2007, Junio C Hamano wrote:\n>\n> > +\t\tif (rev->prune_fn && rev->dense && !(flags & TREECHANGE)) {\n> > +\t\t\tif (commit->parents && !commit->parents->next)\n> > +\t\t\t\tcontinue;\n> > +\t\t}\n> \n> When looking at:\n> \n> \tif (A && B && C) {\n> \tif (D && E)\n> \tcontinue;\n> \t}\n> \n> an uninitiated might say \"Huh? Why use nested 'if'?\", but to\n> somebody who knows how revision traversal works, the above split\n> is a more logical way to test this condition. Maybe one liner\n> comment is in order?\n\nI'd almost prefer not to.\n\nIf people feel the code is subtle enough that a comment is in order to \nexplain *what* something does, I would rather introduce helper functions \nthan add comments. I'm not a big believer in comments in the middle of \ncode to explain the code, but I *am* a big believer in trying to make the \ncode easy to read without them.\n\n(I don't dislike comments per se, but I'd *much* rather have the comments \nexplain what is going on at a higher level. Comments that talk about the \ndetails of the code itself is likely bogus).\n\nSo we could add a commit to say what is going on (\"ignore commits that \nhave only one parent and didn't change the tree\"), but I'd not want to \nexplain why that particular layout of code.\n\nThat said, I've often found the \"TREECHANGE\" bit annoying. The fact that \nwe always have to test it together with testing \"rev->prune_fn\" and often \nalso the \"rev->dense\" flag is just annoying. I'd almost like to just \nalways set the bit if \"rev->prune_fn\" isn't set. Alternatively, the code \ncould be rewritten to just have a few inline helper functions, and it \ncould perhaps be written as\n\n\tif (!(flags & TREECHANGE) && revs->dense && single_parent(commit))\n\t\tcontinue;\n\nI dunno. I have no really *strong* opinions, although I suspect that \nanybody who looks at that particular piece of code had better understand \nthese issues well enough anyway that it doesn't much matter..\n\n> As you noted, this is more like \"Partial output\" now.\n> How about painting the bikeshed pink by saying:\n> \n> \tPartial output: 20\n> Partial output: 70\n> Final output: 70000\n\nI'm fine with it. The reason I did it the way I did was that this way I \ndidn't need to change \"gitk\" - I could just use Pauls original patch \nas-is, since that code didn't care *what* came after the \"Final output\", \nand didn't care how many times it showed up.\n\n\t\t\tLinus\n"},{"id":"58421","messageId":"alpine.LFD.0.999.0711051313350.15101@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711051233270.15101@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Enhance --early-output format","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-05T21:22:34Z","receivedAt":"2007-11-05T21:22:34Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 5 Nov 2007, Linus Torvalds wrote:\n> \n> That said, I've often found the \"TREECHANGE\" bit annoying. The fact that \n> we always have to test it together with testing \"rev->prune_fn\" and often \n> also the \"rev->dense\" flag is just annoying. I'd almost like to just \n> always set the bit if \"rev->prune_fn\" isn't set. Alternatively, the code \n> could be rewritten to just have a few inline helper functions, and it \n> could perhaps be written as\n> \n> \tif (!(flags & TREECHANGE) && revs->dense && single_parent(commit))\n> \t\tcontinue;\n> \n> I dunno.\n\nHere's a possible cleanup patch. It's on top of the enhanced \n--early-output format commit, and in fact fixes a stupid bug in that \ncommit (\"return -1\" vs \"return NULL\"), but that bug-fix is really an \nindependent thing.\n\nIt basically removes the unnecessary indirection of \"revs->prune_fn\", \nsince that function is always the same one (or NULL), and there is in fact \nnot even an abstraction reason to make it a function (ie its not called \nfrom some other file and doesn't allow us to keep the function itself \nstatic or anything like that).\n\nIt then just replaces it with a bit that says \"prune or not\", and if not \npruning, every commit gets TREECHANGE.\n\nThat in turn means that\n\n - if (!revs->prune_fn || (flags & TREECHANGE))\n - if (revs->prune_fn && !(flags & TREECHANGE))\n\njust become\n\n - if (flags & TREECHANGE)\n - if (!(flags & TREECHANGE))\n\nrespectively.\n\nTogether with adding the \"single_parent()\" helper function, the \"complex\" \nconditional now becomes\n\n\tif (!(flags & TREECHANGE) && rev->dense && single_parent(commit))\n\t\tcontinue;\n\nAnyway, do with this as you will. I think it's ok, but apart from passing \nthe test-suite and looking obvious, this has gotten zero testing.\n\n\t\tLinus\n\n---\n builtin-log.c | 6 ++----\n builtin-rev-list.c | 14 +++++++-------\n commit.h | 5 +++++\n revision.c | 20 ++++++++++++--------\n revision.h | 5 +----\n 5 files changed, 27 insertions(+), 23 deletions(-)\n\ndiff --git a/builtin-log.c b/builtin-log.c\nindex 981f388..76c84e2 100644\n--- a/builtin-log.c\n+++ b/builtin-log.c\n@@ -92,10 +92,8 @@ static int estimate_commit_count(struct rev_info *rev, struct commit_list *list)\n \t\tlist = list->next;\n \t\tif (flags & UNINTERESTING)\n \t\t\tcontinue;\n-\t\tif (rev->prune_fn && rev->dense && !(flags & TREECHANGE)) {\n-\t\t\tif (commit->parents && !commit->parents->next)\n-\t\t\t\tcontinue;\n-\t\t}\n+\t\tif (!(flags & TREECHANGE) && rev->dense && single_parent(commit))\n+\t\t\tcontinue;\n \t\tn++;\n \t}\n \treturn n;\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 6970467..2dec887 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -142,7 +142,7 @@ static int count_distance(struct commit_list *entry)\n \n \t\tif (commit->object.flags & (UNINTERESTING | COUNTED))\n \t\t\tbreak;\n-\t\tif (!revs.prune_fn || (commit->object.flags & TREECHANGE))\n+\t\tif (commit->object.flags & TREECHANGE)\n \t\t\tnr++;\n \t\tcommit->object.flags |= COUNTED;\n \t\tp = commit->parents;\n@@ -198,7 +198,7 @@ static inline int halfway(struct commit_list *p, int nr)\n \t/*\n \t * Don't short-cut something we are not going to return!\n \t */\n-\tif (revs.prune_fn && !(p->item->object.flags & TREECHANGE))\n+\tif (!(p->item->object.flags & TREECHANGE))\n \t\treturn 0;\n \tif (DEBUG_BISECT)\n \t\treturn 0;\n@@ -268,7 +268,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)\n \t\tint distance;\n \t\tunsigned flags = p->item->object.flags;\n \n-\t\tif (revs.prune_fn && !(flags & TREECHANGE))\n+\t\tif (!(flags & TREECHANGE))\n \t\t\tcontinue;\n \t\tdistance = weight(p);\n \t\tif (nr - distance < distance)\n@@ -308,7 +308,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n \t\tint distance;\n \t\tunsigned flags = p->item->object.flags;\n \n-\t\tif (revs.prune_fn && !(flags & TREECHANGE))\n+\t\tif (!(flags & TREECHANGE))\n \t\t\tcontinue;\n \t\tdistance = weight(p);\n \t\tif (nr - distance < distance)\n@@ -362,7 +362,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tp->item->util = &weights[n++];\n \t\tswitch (count_interesting_parents(commit)) {\n \t\tcase 0:\n-\t\t\tif (!revs.prune_fn || (flags & TREECHANGE)) {\n+\t\t\tif (flags & TREECHANGE) {\n \t\t\t\tweight_set(p, 1);\n \t\t\t\tcounted++;\n \t\t\t\tshow_list(\"bisection 2 count one\",\n@@ -435,7 +435,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t * add one for p itself if p is to be counted,\n \t\t\t * otherwise inherit it from q directly.\n \t\t\t */\n-\t\t\tif (!revs.prune_fn || (flags & TREECHANGE)) {\n+\t\t\tif (flags & TREECHANGE) {\n \t\t\t\tweight_set(p, weight(q)+1);\n \t\t\t\tcounted++;\n \t\t\t\tshow_list(\"bisection 2 count one\",\n@@ -482,7 +482,7 @@ static struct commit_list *find_bisection(struct commit_list *list,\n \t\t\tcontinue;\n \t\tp->next = last;\n \t\tlast = p;\n-\t\tif (!revs.prune_fn || (flags & TREECHANGE))\n+\t\tif (flags & TREECHANGE)\n \t\t\tnr++;\n \t\ton_list++;\n \t}\ndiff --git a/commit.h b/commit.h\nindex 4ed0c1c..aa67986 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -117,4 +117,9 @@ extern int interactive_add(void);\n extern void add_files_to_cache(int verbose, const char *prefix, const char **files);\n extern int rerere(void);\n \n+static inline int single_parent(struct commit *commit)\n+{\n+\treturn commit->parents && !commit->parents->next;\n+}\n+\n #endif /* COMMIT_H */\ndiff --git a/revision.c b/revision.c\nindex 5d6f208..7a1ecba 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -308,6 +308,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \tstruct commit_list **pp, *parent;\n \tint tree_changed = 0, tree_same = 0;\n \n+\t/*\n+\t * If we don't do pruning, everything is interesting\n+\t */\n+\tif (!revs->prune) {\n+\t\tcommit->object.flags |= TREECHANGE;\n+\t\treturn;\n+\t}\n+\n \tif (!commit->tree)\n \t\treturn;\n \n@@ -415,8 +423,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, str\n \t * simplify the commit history and find the parent\n \t * that has no differences in the path set if one exists.\n \t */\n-\tif (revs->prune_fn)\n-\t\trevs->prune_fn(revs, commit);\n+\ttry_to_simplify_commit(revs, commit);\n \n \tif (revs->no_walk)\n \t\treturn 0;\n@@ -684,9 +691,6 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \trevs->skip_count = -1;\n \trevs->max_count = -1;\n \n-\trevs->prune_fn = NULL;\n-\trevs->prune_data = NULL;\n-\n \trevs->commit_format = CMIT_FMT_DEFAULT;\n \n \tdiff_setup(&revs->diffopt);\n@@ -1271,7 +1275,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \t\tdiff_tree_setup_paths(revs->prune_data, &revs->pruning);\n \t\t/* Can't prune commits with rename following: the paths change.. */\n \t\tif (!revs->diffopt.follow_renames)\n-\t\t\trevs->prune_fn = try_to_simplify_commit;\n+\t\t\trevs->prune = 1;\n \t\tif (!revs->full_diff)\n \t\t\tdiff_tree_setup_paths(revs->prune_data, &revs->diffopt);\n \t}\n@@ -1412,7 +1416,7 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\treturn commit_ignore;\n \tif (!commit_match(commit, revs))\n \t\treturn commit_ignore;\n-\tif (revs->prune_fn && revs->dense) {\n+\tif (revs->prune && revs->dense) {\n \t\t/* Commit without changes? */\n \t\tif (!(commit->object.flags & TREECHANGE)) {\n \t\t\t/* drop merges unless we want parenthood */\n@@ -1460,7 +1464,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\tcase commit_ignore:\n \t\t\tcontinue;\n \t\tcase commit_error:\n-\t\t\treturn -1;\n+\t\t\treturn NULL;\n \t\tdefault:\n \t\t\treturn commit;\n \t\t}\ndiff --git a/revision.h b/revision.h\nindex 2232247..a798514 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -15,8 +15,6 @@\n struct rev_info;\n struct log_info;\n \n-typedef void (prune_fn_t)(struct rev_info *revs, struct commit *commit);\n-\n struct rev_info {\n \t/* Starting list */\n \tstruct commit_list *commits;\n@@ -28,12 +26,11 @@ struct rev_info {\n \t/* Basic information */\n \tconst char *prefix;\n \tvoid *prune_data;\n-\tprune_fn_t *prune_fn;\n-\n \tunsigned int early_output;\n \n \t/* Traversal flags */\n \tunsigned int\tdense:1,\n+\t\t\tprune:1,\n \t\t\tno_merges:1,\n \t\t\tno_walk:1,\n \t\t\tremove_empty_trees:1,\n"},{"id":"58424","messageId":"alpine.LFD.0.999.0711051328140.15101@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711051313350.15101@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Enhance --early-output format","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-05T21:35:31Z","receivedAt":"2007-11-05T21:35:31Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 5 Nov 2007, Linus Torvalds wrote:\n> \n> Here's a possible cleanup patch. It's on top of the enhanced \n> --early-output format commit, and in fact fixes a stupid bug in that \n> commit (\"return -1\" vs \"return NULL\"), but that bug-fix is really an \n> independent thing.\n\n.. and this extends a bit further on the notion.\n\nIt basically means that \"rev->dense\" can now be ignored outside of \nrevision.c, because we'll just set TREECHANGE automatically when \nseeing a non-merge regular commit when --sparse is being used.\n\nSo it's not just a simplification, it's a performance optimization too! \n\nAlthough since nobody sane would ever use --sparse, I guess nobody really \ncares.\n\n\t\tLinus\n\n---\n builtin-log.c | 8 ++------\n revision.c | 9 +++++++++\n 2 files changed, 11 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin-log.c b/builtin-log.c\nindex 76c84e2..d6845bc 100644\n--- a/builtin-log.c\n+++ b/builtin-log.c\n@@ -88,13 +88,9 @@ static int estimate_commit_count(struct rev_info *rev, struct commit_list *list)\n \twhile (list) {\n \t\tstruct commit *commit = list->item;\n \t\tunsigned int flags = commit->object.flags;\n-\n \t\tlist = list->next;\n-\t\tif (flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\tif (!(flags & TREECHANGE) && rev->dense && single_parent(commit))\n-\t\t\tcontinue;\n-\t\tn++;\n+\t\tif ((flags & TREECHANGE) && !(flags & UNINTERESTING))\n+\t\t\tn++;\n \t}\n \treturn n;\n }\ndiff --git a/revision.c b/revision.c\nindex 7a1ecba..02e9241 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -325,6 +325,15 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\treturn;\n \t}\n \n+\t/*\n+\t * Normal non-merge commit? If we don't want to make the \n+\t * history dense, we consider it always to be a change..\n+\t */\n+\tif (!revs->dense && !commit->parents->next) {\n+\t\tcommit->object.flags |= TREECHANGE;\n+\t\treturn;\n+\t}\n+\n \tpp = &commit->parents;\n \twhile ((parent = *pp) != NULL) {\n \t\tstruct commit *p = parent->item;\n"},{"id":"59616","messageId":"alpine.LFD.0.9999.0711122046570.2786@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.999.0711041124050.15101@woody.linux-foundation.org","subject":"[PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-13T04:58:22Z","receivedAt":"2007-11-13T04:58:22Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nWhen we do history simplification in early-output, we end up in the \ninteresting situation that the early output may do simplification with a \npartial tree - in particular, there may be parents that simply haven't \nbeen handled yet, and don't have their parenthood parsed.\n\nThe history simplification would get this case totally wrong, and assume \nthat the parent list of a parent being NULL meant that it was a root \ncommit, and rewrite the whole parent as such.\n\nThis would cause unconnected commits in the gitk output.\n\nThis fixes it, by saying that if you reach a parent that hasn't been \nparsed yet, history simplification will simply stop and leave it alone: \nlater on, when we have the full history, we will *continue* the \nsimplification and eventually get the right information.\n\nHowever, while the parent is now correctly rewritten, it looks like gitk \nis confused by this. Gitk will remember the original parent information, \neven if a replay has given new parenthood information. Since the partial \nearly-output information is triggered by timing, this means that gitk will \nshow some totally random parent that quite possibly won't even be part of \nthe final commit set at all!\n\nOn the kernel, at least with my machine, I can trigger this with something \nlike\n\n\tgitk fs/read_write.c\n\nwhere currently the log (with --parents) reads like this:\n\n\tcommit a16877ca9cec211708a161057a7cbfbf2cbc3a53 d96e6e71647846e0dab097efd9b8bf3a3a556dca\n\tAuthor: Pavel Emelyanov \n\tDate: Mon Oct 1 14:41:11 2007 -0700\n\t\n\t Cleanup macros for distinguishing mandatory locks\n\t..\n\n\tcommit d96e6e71647846e0dab097efd9b8bf3a3a556dca d6b29d7cee064f28ca097e906de7453541351095\n\tAuthor: Jens Axboe \n\tDate: Mon Jun 11 12:18:52 2007 +0200\n\t\n\t Remove remnants of sendfile()\n\t...\n\nbut with early-output (and this fixed patch), I get something like this:\n\n\tFinal output: 1 incomplete\n\tcommit a16877ca9cec211708a161057a7cbfbf2cbc3a53 31b54f40e12e4d04941762be6615edaf3c6ed811\n\tAuthor: Pavel Emelyanov \n\tDate: Mon Oct 1 14:41:11 2007 -0700\n\n\t Cleanup macros for distinguishing mandatory locks\n\t...\n\n\tFinal output: 26 done\n\tcommit a16877ca9cec211708a161057a7cbfbf2cbc3a53 d96e6e71647846e0dab097efd9b8bf3a3a556dca\n\tAuthor: Pavel Emelyanov \n\tDate: Mon Oct 1 14:41:11 2007 -0700\n\t\n\t Cleanup macros for distinguishing mandatory locks\n\t..\n\nie notice how the early-output doesn't have the right parent, since it \nhasn't gotten that far back in history yet. So now the final output will \nhave the parenthood rewritten (correctly), but gitk will have cached the \nold random incorrect parenthood, and doesn't react properly to the updated \nand fixed one at replay time.\n\nAnyway, this is a real fix, but gitk remains a bit useless as is.\n\nSigned-off-by: Linus Torvalds \n---\n revision.c | 2 ++\n 1 files changed, 2 insertions(+), 0 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 931f978..8872a91 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1352,6 +1352,8 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t\tif (!revs->limited)\n \t\t\tif (add_parents_to_list(revs, p, &revs->commits) < 0)\n \t\t\t\treturn rewrite_one_error;\n+\t\tif (!p->object.parsed)\n+\t\t\treturn rewrite_one_ok;\n \t\tif (p->parents && p->parents->next)\n \t\t\treturn rewrite_one_ok;\n \t\tif (p->object.flags & (TREECHANGE | UNINTERESTING))\n"},{"id":"59619","messageId":"7v1wauzomr.fsf@gitster.siamese.dyndns.org","threadId":"10493","inReplyTo":"alpine.LFD.0.9999.0711122046570.2786@woody.linux-foundation.org","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-13T05:43:40Z","receivedAt":"2007-11-13T05:43:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Anyway, this is a real fix, but gitk remains a bit useless as is.\n>\n> Signed-off-by: Linus Torvalds \n> ---\n> revision.c | 2 ++\n> 1 files changed, 2 insertions(+), 0 deletions(-)\n>\n> diff --git a/revision.c b/revision.c\n> index 931f978..8872a91 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -1352,6 +1352,8 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n> \t\tif (!revs->limited)\n> \t\t\tif (add_parents_to_list(revs, p, &revs->commits) < 0)\n> \t\t\t\treturn rewrite_one_error;\n> +\t\tif (!p->object.parsed)\n> +\t\t\treturn rewrite_one_ok;\n> \t\tif (p->parents && p->parents->next)\n> \t\t\treturn rewrite_one_ok;\n> \t\tif (p->object.flags & (TREECHANGE | UNINTERESTING))\n\nThis is too subtle, or I am missing something.\n\nI have to wonder what would happen if a much higher level caller\ncaused the objects to get parsed before coming into the revision\nwalking machinery, e.g. after the command line processing for\nA...B walked the ancestry chain until their common ancestors are\nfound. So these commits between A and B are parsed, but the\nrevision limiting machinery hasn't done its operation to set\nTREECHANGE and/or UNINTERESTING in add_parents_to_list() on\nthese commits yet.\n\nI think the fix will not trigger for such parents, but the\nprocessing just goes on.\n"},{"id":"59620","messageId":"alpine.LFD.0.9999.0711122238330.2786@woody.linux-foundation.org","threadId":"10493","inReplyTo":"7v1wauzomr.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-13T06:46:16Z","receivedAt":"2007-11-13T06:46:16Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 12 Nov 2007, Junio C Hamano wrote:\n> \n> This is too subtle, or I am missing something.\n\nIt's subtle. And you're probably right, I need to fix it up some more.\n\nIt works, but it works for all the wrong reasons. When thinking about it, \nyou need to keep three \"generations\" of commits in mind. Let's call them \n\"c\" (commit), \"p\" (parent of c) and \"pp\" (parent of p) respectively.\n\nWhat is going on is:\n - we have calculated TREECHANGE for \"c\".\n - that, in turn, means that we have parsed \"p\" (it's done by \n add_parents_to_list() - either as part of try_to_simplify_commit(), or \n if that code doesn't trigger, by the later loop over the parents)\n - but we haven't parsed \"pp\" yet.\n\nNow, when we decide to rewrite \"c\", we look at whether we can change the \nparent list of c to point from \"p\" to \"pp\". But with the added check, we \nnow will trigger on the fact that \"pp\" hasn't even been parsed yet, so we \nwon't even try, and we leave the parent list alone.\n\nBut I agree, I don't think it's really stable. We could have gotten to \n\"pp\" through some other chain.\n\nI think the real problem is that \"TREECHANGE\" has the wrong polarity. It \nshould default to always being set, and then we could actively clear it \nwhen we do the work to say \"it's the same tree\". Instead, we default it to \nbeing the same (which triggers parent rewriting), and only later may we \nnotice that it wasn't the same.\n\n\t\t\tLinus\n"},{"id":"59621","messageId":"alpine.LFD.0.9999.0711122309270.2786@woody.linux-foundation.org","threadId":"10493","inReplyTo":"alpine.LFD.0.9999.0711122238330.2786@woody.linux-foundation.org","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-13T07:16:08Z","receivedAt":"2007-11-13T07:16:08Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 12 Nov 2007, Linus Torvalds wrote:\n> \n> I think the real problem is that \"TREECHANGE\" has the wrong polarity. It \n> should default to always being set, and then we could actively clear it \n> when we do the work to say \"it's the same tree\". Instead, we default it to \n> being the same (which triggers parent rewriting), and only later may we \n> notice that it wasn't the same.\n\nSo, maybe the proper solution is to say \"commits are assumed to be \ndifferent to their parents, but we have an explicit bit saying TREESAME \nwhen we find them to be the same\".\n\nThis solves the problem quite naturally, because any tree that hasn't been \nparsed - or even if it *has* been parsed, but just hasn't gone through \nthe compare function - will then always be seen as \"different\" and thus \ninteresting.\n\nThis fairly straight-forward patch seems to work. It *replaces* the \npervious \"patch 4/2\", and yes, Junio, I think you were very right to \ncomplain about that one.\n\nHow does this one feel? It basically says \"a commit that has TREESAME set \nis kind-of-UNINTERESTING\", but obviously in a different way than an \noutright UNINTERESTING commit.\n\nThe diff is pretty straightforward - just change the sense of TREECHANGE, \nand that sometimes removes a line, and sometimes adds one, but most of the \nchanges are just TREECHANGE => TREESAME, together with a negation of the \noperation.\n\n\t\tLinus\n\n---\n builtin-fmt-merge-msg.c | 2 +-\n builtin-log.c | 2 +-\n builtin-rev-list.c | 16 ++++++++--------\n revision.c | 22 +++++++++++-----------\n revision.h | 2 +-\n 5 files changed, 22 insertions(+), 22 deletions(-)\n\ndiff --git a/builtin-fmt-merge-msg.c b/builtin-fmt-merge-msg.c\nindex 8a3c962..6163bd4 100644\n--- a/builtin-fmt-merge-msg.c\n+++ b/builtin-fmt-merge-msg.c\n@@ -176,7 +176,7 @@ static void shortlog(const char *name, unsigned char *sha1,\n \tstruct commit *commit;\n \tstruct object *branch;\n \tstruct list subjects = { NULL, NULL, 0, 0 };\n-\tint flags = UNINTERESTING | TREECHANGE | SEEN | SHOWN | ADDED;\n+\tint flags = UNINTERESTING | TREESAME | SEEN | SHOWN | ADDED;\n \n \tbranch = deref_tag(parse_object(sha1), sha1_to_hex(sha1), 40);\n \tif (!branch || branch->type != OBJ_COMMIT)\ndiff --git a/builtin-log.c b/builtin-log.c\nindex d6845bc..54ddaad 100644\n--- a/builtin-log.c\n+++ b/builtin-log.c\n@@ -89,7 +89,7 @@ static int estimate_commit_count(struct rev_info *rev, struct commit_list *list)\n \t\tstruct commit *commit = list->item;\n \t\tunsigned int flags = commit->object.flags;\n \t\tlist = list->next;\n-\t\tif ((flags & TREECHANGE) && !(flags & UNINTERESTING))\n+\t\tif (!(flags & (TREESAME | UNINTERESTING)))\n \t\t\tn++;\n \t}\n \treturn n;\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 2dec887..0258ec4 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -142,7 +142,7 @@ static int count_distance(struct commit_list *entry)\n \n \t\tif (commit->object.flags & (UNINTERESTING | COUNTED))\n \t\t\tbreak;\n-\t\tif (commit->object.flags & TREECHANGE)\n+\t\tif (!(commit->object.flags & TREESAME))\n \t\t\tnr++;\n \t\tcommit->object.flags |= COUNTED;\n \t\tp = commit->parents;\n@@ -198,7 +198,7 @@ static inline int halfway(struct commit_list *p, int nr)\n \t/*\n \t * Don't short-cut something we are not going to return!\n \t */\n-\tif (!(p->item->object.flags & TREECHANGE))\n+\tif (p->item->object.flags & TREESAME)\n \t\treturn 0;\n \tif (DEBUG_BISECT)\n \t\treturn 0;\n@@ -234,7 +234,7 @@ static void show_list(const char *debug, int counted, int nr,\n \t\tchar *ep, *sp;\n \n \t\tfprintf(stderr, \"%c%c%c \",\n-\t\t\t(flags & TREECHANGE) ? 'T' : ' ',\n+\t\t\t(flags & TREESAME) ? ' ' : 'T',\n \t\t\t(flags & UNINTERESTING) ? 'U' : ' ',\n \t\t\t(flags & COUNTED) ? 'C' : ' ');\n \t\tif (commit->util)\n@@ -268,7 +268,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)\n \t\tint distance;\n \t\tunsigned flags = p->item->object.flags;\n \n-\t\tif (!(flags & TREECHANGE))\n+\t\tif (flags & TREESAME)\n \t\t\tcontinue;\n \t\tdistance = weight(p);\n \t\tif (nr - distance < distance)\n@@ -308,7 +308,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n \t\tint distance;\n \t\tunsigned flags = p->item->object.flags;\n \n-\t\tif (!(flags & TREECHANGE))\n+\t\tif (flags & TREESAME)\n \t\t\tcontinue;\n \t\tdistance = weight(p);\n \t\tif (nr - distance < distance)\n@@ -362,7 +362,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tp->item->util = &weights[n++];\n \t\tswitch (count_interesting_parents(commit)) {\n \t\tcase 0:\n-\t\t\tif (flags & TREECHANGE) {\n+\t\t\tif (!(flags & TREESAME)) {\n \t\t\t\tweight_set(p, 1);\n \t\t\t\tcounted++;\n \t\t\t\tshow_list(\"bisection 2 count one\",\n@@ -435,7 +435,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t * add one for p itself if p is to be counted,\n \t\t\t * otherwise inherit it from q directly.\n \t\t\t */\n-\t\t\tif (flags & TREECHANGE) {\n+\t\t\tif (!(flags & TREESAME)) {\n \t\t\t\tweight_set(p, weight(q)+1);\n \t\t\t\tcounted++;\n \t\t\t\tshow_list(\"bisection 2 count one\",\n@@ -482,7 +482,7 @@ static struct commit_list *find_bisection(struct commit_list *list,\n \t\t\tcontinue;\n \t\tp->next = last;\n \t\tlast = p;\n-\t\tif (flags & TREECHANGE)\n+\t\tif (!(flags & TREESAME))\n \t\t\tnr++;\n \t\ton_list++;\n \t}\ndiff --git a/revision.c b/revision.c\nindex 931f978..5796153 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -311,17 +311,15 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t/*\n \t * If we don't do pruning, everything is interesting\n \t */\n-\tif (!revs->prune) {\n-\t\tcommit->object.flags |= TREECHANGE;\n+\tif (!revs->prune)\n \t\treturn;\n-\t}\n \n \tif (!commit->tree)\n \t\treturn;\n \n \tif (!commit->parents) {\n-\t\tif (!rev_same_tree_as_empty(revs, commit->tree))\n-\t\t\tcommit->object.flags |= TREECHANGE;\n+\t\tif (rev_same_tree_as_empty(revs, commit->tree))\n+\t\t\tcommit->object.flags |= TREESAME;\n \t\treturn;\n \t}\n \n@@ -329,10 +327,8 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t * Normal non-merge commit? If we don't want to make the\n \t * history dense, we consider it always to be a change..\n \t */\n-\tif (!revs->dense && !commit->parents->next) {\n-\t\tcommit->object.flags |= TREECHANGE;\n+\tif (!revs->dense && !commit->parents->next)\n \t\treturn;\n-\t}\n \n \tpp = &commit->parents;\n \twhile ((parent = *pp) != NULL) {\n@@ -357,6 +353,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t\t}\n \t\t\tparent->next = NULL;\n \t\t\tcommit->parents = parent;\n+\t\t\tcommit->object.flags |= TREESAME;\n \t\t\treturn;\n \n \t\tcase REV_TREE_NEW:\n@@ -385,7 +382,8 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\tdie(\"bad tree compare for commit %s\", sha1_to_hex(commit->object.sha1));\n \t}\n \tif (tree_changed && !tree_same)\n-\t\tcommit->object.flags |= TREECHANGE;\n+\t\treturn;\n+\tcommit->object.flags |= TREESAME;\n }\n \n static int add_parents_to_list(struct rev_info *revs, struct commit *commit, struct commit_list **list)\n@@ -1354,7 +1352,9 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t\t\t\treturn rewrite_one_error;\n \t\tif (p->parents && p->parents->next)\n \t\t\treturn rewrite_one_ok;\n-\t\tif (p->object.flags & (TREECHANGE | UNINTERESTING))\n+\t\tif (p->object.flags & UNINTERESTING)\n+\t\t\treturn rewrite_one_ok;\n+\t\tif (!(p->object.flags & TREESAME))\n \t\t\treturn rewrite_one_ok;\n \t\tif (!p->parents)\n \t\t\treturn rewrite_one_noparents;\n@@ -1427,7 +1427,7 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\treturn commit_ignore;\n \tif (revs->prune && revs->dense) {\n \t\t/* Commit without changes? */\n-\t\tif (!(commit->object.flags & TREECHANGE)) {\n+\t\tif (commit->object.flags & TREESAME) {\n \t\t\t/* drop merges unless we want parenthood */\n \t\t\tif (!revs->parents)\n \t\t\t\treturn commit_ignore;\ndiff --git a/revision.h b/revision.h\nindex a798514..992e1e9 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -3,7 +3,7 @@\n \n #define SEEN\t\t(1u<<0)\n #define UNINTERESTING (1u<<1)\n-#define TREECHANGE\t(1u<<2)\n+#define TREESAME\t(1u<<2)\n #define SHOWN\t\t(1u<<3)\n #define TMP_MARK\t(1u<<4) /* for isolated cases; clean after use */\n #define BOUNDARY\t(1u<<5)\n"},{"id":"59627","messageId":"20071113075341.GN2261MdfPADPa@greensroom.kotnet.org","threadId":"10493","inReplyTo":"alpine.LFD.0.9999.0711122309270.2786@woody.linux-foundation.org","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Sven Verdoolaege","fromEmail":"skimo@kotnet.org","sentAt":"2007-11-13T07:53:41Z","receivedAt":"2007-11-13T07:53:41Z","isPatch":true,"sender":{"key":"skimo@kotnet.org","avatar":null},"body":"On Mon, Nov 12, 2007 at 11:16:08PM -0800, Linus Torvalds wrote:\n> On Mon, 12 Nov 2007, Linus Torvalds wrote:\n> > \n> > I think the real problem is that \"TREECHANGE\" has the wrong polarity. It \n> > should default to always being set, and then we could actively clear it \n> > when we do the work to say \"it's the same tree\". Instead, we default it to \n> > being the same (which triggers parent rewriting), and only later may we \n> > notice that it wasn't the same.\n> \n> So, maybe the proper solution is to say \"commits are assumed to be \n> different to their parents, but we have an explicit bit saying TREESAME \n> when we find them to be the same\".\n\nFWIW, I like it.\n\nI had basically the same patch in my git-rewrite-commits series\n(except that I called it \"PRUNED\" instead of \"TREESAME\"), but I\ndon't think I even sent it to the list, because I was told there\nwas no use.\n\nskimo\n"},{"id":"59629","messageId":"20071113080125.GB14735@spearce.org","threadId":"10493","inReplyTo":"7v1wauzomr.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-11-13T08:01:25Z","receivedAt":"2007-11-13T08:01:25Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> I have to wonder what would happen if a much higher level caller\n> caused the objects to get parsed before coming into the revision\n> walking machinery, e.g. after the command line processing for\n> A...B walked the ancestry chain until their common ancestors are\n> found. So these commits between A and B are parsed, but the\n> revision limiting machinery hasn't done its operation to set\n> TREECHANGE and/or UNINTERESTING in add_parents_to_list() on\n> these commits yet.\n\nThat's one of the problems with the way the revision walking\nmachinery is built. Its fast, but it can really only be used once.\nMy series about making the allocators able to free their nodes was\nto allow resetting the entire machinary for another user, but as you\npointed out how do we decide when we can do a reset and invalidate\nall prior struct commit*?\n\n-- \nShawn.\n"},{"id":"59631","messageId":"7vabpiv9go.fsf@gitster.siamese.dyndns.org","threadId":"10493","inReplyTo":"20071113080125.GB14735@spearce.org","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-13T08:24:55Z","receivedAt":"2007-11-13T08:24:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> Junio C Hamano wrote:\n>\n>> I have to wonder what would happen if a much higher level caller\n>> caused the objects to get parsed before coming into the revision\n>> walking machinery, e.g. after the command line processing for\n>> A...B walked the ancestry chain until their common ancestors are\n>> found. So these commits between A and B are parsed, but the\n>> revision limiting machinery hasn't done its operation to set\n>> TREECHANGE and/or UNINTERESTING in add_parents_to_list() on\n>> these commits yet.\n>\n> That's one of the problems with the way the revision walking\n> machinery is built. Its fast, but it can really only be used once.\n\nYes but not quite. As long as you do not use overlapping set of\nflag bits without cleaning, you are almost Ok.\n\nThe reason I say \"almost\" is that I think the true problem with\nthe first patch by Linus was to load \"parsed\" bit any semantics\nother than \"we have read and parsed the data so do not bother\nrereading it\". If it used another mechanism (e.g. another flag\nbit that means \"we have done TREECHANGE and stuff\"), returning\nrewrite_one_ok to punt when seeing an unprocessed node would\nhave been safe, as it would not have munged the parent list.\nThe replacement \"TREESAME\" patch would work much better without\nusing such an extra bit, because it allows us to directly check\n\"if we already decided this does not change from the parent\",\nand the lack of the bit covers both \"we haven't processed it\"\nand \"we processed but we do not want to prune\" cases, and not\npruning is safe and easily and correctly re-processible in the\npost clean-up phase of the early_output series.\n\nBut in general, you're right. An operation that changes the\nancestry shape is irreversible, and you would need to cause\nreparsing of the commit objects after you are done with revision\ntraversal, and at that point, discarding and re-reading\neverything from scratch, although is heavy-handed, is one\nplausible approach to tackle the problem.\n"},{"id":"59634","messageId":"7v1wauv8dr.fsf@gitster.siamese.dyndns.org","threadId":"10493","inReplyTo":"alpine.LFD.0.9999.0711122309270.2786@woody.linux-foundation.org","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-13T08:48:16Z","receivedAt":"2007-11-13T08:48:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> This solves the problem quite naturally, because any tree that hasn't been \n> parsed - or even if it *has* been parsed, but just hasn't gone through \n> the compare function - will then always be seen as \"different\" and thus \n> interesting.\n>\n> This fairly straight-forward patch seems to work. It *replaces* the \n> pervious \"patch 4/2\", and yes, Junio, I think you were very right to \n> complain about that one.\n>\n> How does this one feel?\n\nI think this is very natural and I like it.\n\nI did not complain but just said I was puzzled, but after\nthinking about this a bit I probably should have ;-).\n"},{"id":"59642","messageId":"18233.30098.470244.421468@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"alpine.LFD.0.9999.0711122046570.2786@woody.linux-foundation.org","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-11-13T09:59:46Z","receivedAt":"2007-11-13T09:59:46Z","isPatch":true,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> However, while the parent is now correctly rewritten, it looks like gitk \n> is confused by this. Gitk will remember the original parent information, \n> even if a replay has given new parenthood information. Since the partial \n> early-output information is triggered by timing, this means that gitk will \n> show some totally random parent that quite possibly won't even be part of \n> the final commit set at all!\n\nYep. It will be a little complex to deal with that because there are\nbits of state that I set up for the parents, and if they're the wrong\nparents, I'll have to go back and undo that.\n\nIn fact it would be easier for me if, instead of getting the id of\nsome random ancestor commit, I got an explicit indication to say\n\"unknown parent\", such as just a \"-\" in place of the id of the\nunknown parent(s). Would that be doable? I could then just not do\nthe processing for any unknown parent, and make sure to do it when I\nsee the final version of the commit.\n\nAlso, I have just about worked out an efficient way to do the commit\nreordering incrementally, which would let me not use --topo-order or\n--date-order, and display commits as they come in. I'll have to see\nwhether that turns out to be better overall than using --early-output.\n\nPaul.\n"},{"id":"59690","messageId":"7vbq9yt1te.fsf@gitster.siamese.dyndns.org","threadId":"10493","inReplyTo":"18233.30098.470244.421468@cargo.ozlabs.ibm.com","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-13T18:53:01Z","receivedAt":"2007-11-13T18:53:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Paul Mackerras writes:\n\n> In fact it would be easier for me if, instead of getting the id of\n> some random ancestor commit, I got an explicit indication to say\n> \"unknown parent\", such as just a \"-\" in place of the id of the\n> unknown parent(s). Would that be doable? I could then just not do\n> the processing for any unknown parent, and make sure to do it when I\n> see the final version of the commit.\n\nI suspect that a \"-\" in place of a commit object name may not be\nenough for your purpose, as the _number_ of parents can later\nchange in the later re-output.\n\nI wonder if the presense of \"incomplete\" on the \"Final output\"\nline is a good enough indication for that. That is, until you\nsee \"Final output: $N done\", you will treat the parent\ninformation as unreliable.\n"},{"id":"59753","messageId":"18234.7494.851156.347578@cargo.ozlabs.ibm.com","threadId":"10493","inReplyTo":"7vbq9yt1te.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2007-11-13T21:55:18Z","receivedAt":"2007-11-13T21:55:18Z","isPatch":true,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Junio C Hamano writes:\n\n> I suspect that a \"-\" in place of a commit object name may not be\n> enough for your purpose, as the _number_ of parents can later\n> change in the later re-output.\n\nI don't mind if a commit that has \"-\" as one of its parents later\nturns out to have more parents (i.e. the \"-\" can stand for zero or\nmore unknown parents). I would be perturbed if a commit that didn't\nhave any \"-\" in its parent list later turned out to have a different\nnumber of parents - but I don't think that's what you're implying, is\nit?\n\n> I wonder if the presense of \"incomplete\" on the \"Final output\"\n> line is a good enough indication for that. That is, until you\n> see \"Final output: $N done\", you will treat the parent\n> information as unreliable.\n\nThe easiest way for me to handle an unreliable parent is just to\nignore it. But I can't ignore all the parents, because then I\nwouldn't have a graph at all.\n\nIn other words, the presence of \"incomplete\" doesn't give me any clue\nas to which particular parent ids are reliable. As far as I can see,\ngit log internally knows when a parent id is unreliable (it's one\nwhere it had to terminate the history simplification early), so it\nshouldn't be hard to tell gitk about that. And it would make my job a\nlot easier.\n\nPaul.\n"},{"id":"60061","messageId":"e5bfff550711152330m401c39e8g7a2ff7be834f0d56@mail.gmail.com","threadId":"10493","inReplyTo":"18233.30098.470244.421468@cargo.ozlabs.ibm.com","subject":"Re: [PATCH 4/2] Fix parent rewriting in --early-output","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-11-16T07:30:55Z","receivedAt":"2007-11-16T07:30:55Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 11/13/07, Paul Mackerras wrote:\n> Linus Torvalds writes:\n>\n> > However, while the parent is now correctly rewritten, it looks like gitk\n> > is confused by this. Gitk will remember the original parent information,\n> > even if a replay has given new parenthood information. Since the partial\n> > early-output information is triggered by timing, this means that gitk will\n> > show some totally random parent that quite possibly won't even be part of\n> > the final commit set at all!\n>\n> Yep. It will be a little complex to deal with that because there are\n> bits of state that I set up for the parents, and if they're the wrong\n> parents, I'll have to go back and undo that.\n>\n\nSorry to comment on a gitk thread, but the problem of different\nparents for the same sha while replaying was hitted by me also with\nqgit when tring to implement --early-output\n\nI don't know if i is suitable also for gitk but in qgit I changed the\nmatch algorithm to check also for same parents and not only for same\nsha during a replay to detect something has changed, so to catch\ndifferent parents cases early on and avoiding \"going back\" that is\ncomplex.\n\nIOW when git log print outs a replay qgit enter in a state where it\nchecks all the arrived sha against the already sent ones and at the\nfirst mismatch flushes the tail at the point of mismatch.\n\nThe modified algorithm instead of chek just the sha checks also\nparents info (because git log is called with --parents option this\nends up comparing the first line of the commit message).\n\nMarco\n"}]}