git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
From: Linus Torvalds <torvalds@osdl.org>
To: David Woodhouse <dwmw2@infradead.org>
Cc: Junio C Hamano <junkio@cox.net>, Petr Baudis <pasky@ucw.cz>, git@vger.kernel.org
Subject: Re: Merge with git-pasky II.
Date: Fri, 15 Apr 2005 08:32:46 -0700 (PDT)
Message-ID: <Pine.LNX.4.58.0504150753440.7211@ppc970.osdl.org> (raw)
In-Reply-To: <1113559330.12012.292.camel@baythorne.infradead.org>



On Fri, 15 Apr 2005, David Woodhouse wrote:
> 
> And you're right; it shouldn't have to be for renames only. There's no
> need for us to limit it to one "source" and one "destination"; the SCM
> can use it to track content as it sees fit.

Listen to yourself, and think about the problem for a second.

First off, let's just posit that "files" do not matter. The only thing
that matters is how "content" moved in the tree. Ok? If I copy a function
from one fiel to another, the perfect SCM will notice that, and show it as
a diff that removes it from one file and adds it to another, and is
_still_ able to track authorship past the move. Agreed?

Now, you basically propose to put that information in the "commit" log, 
and that's certainly valid. You can have the commit log say "lines 50-89 
in file kernel/sched.c moved to lines 100-139 in kernel/timer.c", and then 
renames fall out of that as one very small special case.

You can even say "lines 50-89 in file kernel/sched.c copied to.." and 
allow data to be tracked past not just movement, but also duplication.

Do you agree that this is kind of what you'd want to aim for? That's a 
winning SCM concept.

How do you think the SCM _gets_ at this information? In particular, how 
are you proposing that we determine this, especially since 90% of all 
stuff comes in as patches etc? 

You propose that we spend time when generating the tree on doing so. I'm 
telling you that that is wrong, for several reasons:

 - you're ignoring different paths for the same data. For example, you 
   will make it impossible to merge two trees that have done exactly the 
   same thing, except one did it as a patch (create/delete) and one did it 
   using some other heuristic.

 - you're doing the work at the wrong point. Doing it _well_ is quite 
   expensive. So if you do it at commit time, you cannot _afford_ to do it 
   well, and you'll always fall back to doing an ass-backwards job that 
   doesn't really get you to the good state, and only gets you to a 
   not-very-interesting easy 1% of the solution (ie full file renames).

 - you're doing the work at the wrong point for _another_ reason. You're 
   freezing your (crappy) algorithm at tree creation time, and basically 
   making it pointless to ever create something better later, because even 
   if hardware and software improves, you've codified that "we have to
   have crappy information".

Now, look at my proposal: 

 - the actual information tracking tracks _nothing_ but information. You 
   have an SCM that tracks what changed at the only level that really 
   matters, namely the whole project. None of the information actually 
   makes any sense at all at a smaller granularity, since by definition, a
   "project" depends on the other files, or it wouldn't be a project, it
   would be _two_ projects or more.

 - When you're interested in the history of the information, you actually 
   track it, and you try to be _intelligent_ about it. You can actually do 
   a HELL of a lot better than whet you propose if you go the extra mile. 
   For example, let's say that you have a visualization tool that you can 
   use for finding out where a line of code came from. You start out at 
   some arbitrary point in the tree, and you drill down. That's how it 
   works, right?

   So how do you drill down? You simply go backwards in history for that 
   project, tracking when that file+line changed (a "file+line" thing is 
   actually a "sensible" tracking unit at this point, because it makes
   sense within the query you're doing - it's _not_ a sensible thing to
   track at "commit" time, but when you ask yourself "where did this line
   come from", that _question_ makes it sensible. Also note that "where 
   did this _file_ come from is not a sensible question, since the file 
   may have been the combination (or split) of several files, so there is
   no _answer_ to that question"

   So the question then becomes: "how can you reasonably _efficiently_
   find the history of one particular line", and in fact it turns out that 
   by asking the question that way, it's pretty obvious: now that you
   don't have to track the whole repository, you can always try to 
   minimize the thing you're looking for.

   So what you do is walk back the history, and look at the tree objects 
   (both sides when you hit a merge), eand see if that file ever changes. 
   That's actually a very efficient operation in GIT - it matches
   _exactly_ how git tracks things anyway. So it's not expensive at all.

   When that file changes, you need to look if that _line_ changed (and 
   here is where it comes down to usability: from a practical standpoint
   you probably don't care about a single line, you really _probably_ want
   to see changes around it too). So you diff the old state and the new 
   state, and you see if you can still find where you were. If you still 
   can, and the line (and a few lines around it) is still the same, you 
   just continue to drill down. So that's not the interesting case.

   So what happens when you found "ok, that area changed"? Your 
   visualization tool now shows it to the user, AND BECAUSE IT SEES THE 
   WHOLE TREE DIFF, it also shows where it probably came from. At _that_ 
   point, it is actually very trivial to use a modest amount of CPU time, 
   and look for probable sources within that diff. You can do it on modern 
   hardware in basically no time, so your visualization tool can actually 
   notice that
 
	"oops, that line didn't even exist in the previous version, BUT I
	 FOUND FIVE PLACES that matched almost perfectly in the same diff,
	 and here they are"

   and voila, your tool now very efficiently showed the programmer that
   the source of the line in question was actually that we had merged 5 
   copies of the same code in different archtiectures into one common
   helper function.

   And if you didn't find some source that matched, or if the old file was
   actually very similar around that line, and that line hadn't been
   "totally new"? That's the easy case again - you show the programmer the
   diff at that point in time, and you let him decide whether that diff 
   was what he was looking for, or whether he wants to continue to "zoom
   down" into the history.

The above tool is (a) fairly easy to write for git (if you can do 
visualization tools and (b) _exactly_ what I think most programmers 
actually want. Tell me I'm wrong. Honestly..

And notice? My clearly _superior_ algorithm never needed any rename
information at all. It would have been a total waste of time. It would
also have hidden the _real_ pattern, which was that a piece of code was
merged from several other matching pieces of code into one new helper
function. But if it _had_ been a pure rename, my superior tool would have
trivially found that _too_. So rename infomation really really doesn't
matter.

So I'm claiming that any SCM that tries to track renames is fundamentally
broken unless it does so for internal reasons (ie to allow efficient
deltas), exactly because renames do not matter. They don't help you, and 
they aren't what you were interested in _anyway_.

What matters is finding "where did this come from", and the git
architecture does that very well indeed - much better than anything else
out there. I outlined a simple algorithm that can be fairly trivially
coded up by somebody who really cares. Sure, pattern matching isn't
trivial, but you start out with just saying "let's find that exact line,
and two lines on each side", and then you start improving on that.

And that "where did this come from" decision should be done at _search_ 
time, not commit time. Because at that time it's not only trivial to do, 
but at that time you can _dynamically_ change your search criteria. For 
example, you can make the "match" algorithm be dependent on what you are 
looking at.

If it's C source code, it might want to ignore vairable names when it
searches for matching code. And if it's a OpenOffice document, you might
have some open-office-specific tools to do so. See? Also, the person doing 
the searches can say whether he is interested in that particular line (or 
even that particial _identifier_ on a line), or whether he wants to see 
the changes "around" that line.

All of which are very valid things to do, and all of which my world-view
supports very well indeed. And all of which your pitiful "files matter" 
world-view totally doesn't get at all.

In other words, I'm right. I'm always right, but sometimes I'm more right 
than other times. And dammit, when I say "files don't matter", I'm really 
really Right(tm).

Please stop this "track files" crap. Git tracks _exactly_ what matters, 
namely "collections of files". Nothing else is relevant, and even 
_thinking_ that it is relevant only limits your world-view. Notice how the 
notion of CVS "annotate" always inevitably ends up limiting how people use 
it. I think it's a totally useless piece of crap, and I've described 
something that I think is a million times more useful, and it all fell out 
_exactly_ because I'm not limiting my thinking to the wrong model of the 
world.

			Linus

  reply index

Thread overview: 148+ messages in thread (expand / mbox.gz / Atom feed / [top])
2005-04-14  0:29 Petr Baudis
2005-04-13 21:25 ` Christopher Li
2005-04-14  0:45   ` Petr Baudis
2005-04-13 22:00     ` Christopher Li
2005-04-14  3:51     ` Linus Torvalds
2005-04-14  1:23       ` Christopher Li
2005-04-14  5:03         ` Paul Jackson
2005-04-14  2:16           ` Christopher Li
2005-04-14  6:16             ` Paul Jackson
2005-04-14  7:05       ` Junio C Hamano
2005-04-14  8:06         ` Linus Torvalds
2005-04-14  8:39           ` Junio C Hamano
2005-04-14  9:10             ` Linus Torvalds
2005-04-14 11:14               ` Junio C Hamano
2005-04-14 12:16                 ` Petr Baudis
2005-04-14 18:12                   ` Junio C Hamano
2005-04-14 18:36                     ` Linus Torvalds
2005-04-14 19:59                       ` Junio C Hamano
2005-04-14 20:20                         ` Petr Baudis
2005-04-15  0:42                         ` Linus Torvalds
2005-04-15  2:33                           ` Barry Silverman
2005-04-15 10:02                           ` David Woodhouse
2005-04-15 15:32                             ` Linus Torvalds [this message]
2005-04-15 16:01                               ` David Woodhouse
2005-04-15 16:31                                 ` C. Scott Ananian
2005-04-15 17:11                                   ` Linus Torvalds
2005-04-16 15:33                                 ` Johannes Schindelin
2005-04-17 13:14                                   ` David Woodhouse
2005-04-15 19:20                               ` Paul Jackson
2005-04-16  1:44                               ` simon
2005-04-16 12:19                                 ` David Lang
2005-04-16 15:55                                   ` Simon Fowler
2005-04-16 16:03                                     ` Petr Baudis
2005-04-16 16:26                                       ` Simon Fowler
2005-04-16 16:26                                       ` Linus Torvalds
2005-04-16 23:02                                         ` David Lang
2005-04-17 14:52                                         ` Ingo Molnar
2005-04-17 15:08                                           ` Brad Roberts
2005-04-17 15:18                                             ` Ingo Molnar
2005-04-17 15:28                                           ` Ingo Molnar
2005-04-17 17:34                                             ` Linus Torvalds
2005-04-17 22:12                                               ` Herbert Xu
2005-04-17 22:35                                                 ` Linus Torvalds
2005-04-17 23:29                                                   ` Herbert Xu
2005-04-17 23:34                                                     ` Petr Baudis
2005-04-17 23:53                                                       ` Kenneth Johansson
2005-04-18  0:49                                                       ` Herbert Xu
2005-04-18  0:55                                                         ` Petr Baudis
2005-04-17 23:50                                                     ` Linus Torvalds
2005-04-18  4:16                                               ` Sanjoy Mahajan
2005-04-18  7:42                                               ` Ingo Molnar
2005-04-16 20:29                               ` Sanjoy Mahajan
2005-04-16 20:41                                 ` Linus Torvalds
2005-04-15  2:21                       ` [Patch] ls-tree enhancements Junio C Hamano
2005-04-15 16:13                         ` Petr Baudis
2005-04-15 18:25                           ` Junio C Hamano
2005-04-15  9:14                       ` Merge with git-pasky II David Woodhouse
2005-04-15  9:36                         ` Ingo Molnar
2005-04-15 10:05                           ` David Woodhouse
2005-04-15 14:53                             ` Ingo Molnar
2005-04-15 15:09                               ` David Woodhouse
2005-04-15 12:03                         ` Johannes Schindelin
2005-04-15 10:22                           ` Theodore Ts'o
2005-04-15 14:53                         ` Linus Torvalds
2005-04-15 15:29                           ` David Woodhouse
2005-04-15 15:51                             ` Linus Torvalds
2005-04-15 15:54                           ` Paul Jackson
2005-04-15 16:30                             ` C. Scott Ananian
2005-04-15 18:29                               ` Paul Jackson
2005-04-14 18:51                     ` Christopher Li
2005-04-14 19:35                     ` Petr Baudis
2005-04-14 20:01                       ` Live Merging from remote repositories Barry Silverman
2005-04-14 23:22                         ` Junio C Hamano
2005-04-15  1:07                           ` Question about git process model Barry Silverman
2005-04-14 20:23                       ` Re: Merge with git-pasky II Erik van Konijnenburg
2005-04-14 20:24                         ` Petr Baudis
2005-04-14 23:12                       ` Junio C Hamano
2005-04-14 20:24                         ` Christopher Li
2005-04-14 23:31                         ` Petr Baudis
2005-04-14 20:30                           ` Christopher Li
2005-04-14 20:37                             ` Christopher Li
2005-04-14 20:50                               ` Christopher Li
2005-04-15  0:58                           ` Junio C Hamano
2005-04-14 22:30                             ` Christopher Li
2005-04-15  7:43                               ` Junio C Hamano
2005-04-15  6:28                                 ` Christopher Li
2005-04-15 11:11                                   ` Junio C Hamano
     [not found]                                     ` <7vaco0i3t9.fsf_-_@assigned-by-dhcp.cox.net>
2005-04-15 18:44                                       ` write-tree is pasky-0.4 Linus Torvalds
2005-04-15 18:56                                         ` Petr Baudis
2005-04-15 20:13                                           ` Linus Torvalds
2005-04-15 22:36                                             ` Petr Baudis
2005-04-16  0:22                                               ` Linus Torvalds
2005-04-16  1:13                                                 ` Daniel Barkalow
2005-04-16  2:18                                                   ` Linus Torvalds
2005-04-16  2:49                                                     ` Daniel Barkalow
2005-04-16  3:13                                                       ` Linus Torvalds
2005-04-16  3:56                                                         ` Daniel Barkalow
2005-04-16  6:59                                                         ` Paul Jackson
2005-04-16 15:34                                                 ` Re: Re: " Petr Baudis
2005-04-15 20:10                                         ` Junio C Hamano
2005-04-15 20:58                                           ` C. Scott Ananian
2005-04-15 21:22                                             ` Petr Baudis
2005-04-15 23:16                                             ` Junio C Hamano
2005-04-15 21:48                                           ` [PATCH 1/2] merge-trees script for Linus git Junio C Hamano
2005-04-15 21:54                                             ` [PATCH 2/2] " Junio C Hamano
2005-04-15 23:33                                             ` [PATCH 3/2] " Junio C Hamano
2005-04-16  1:02                                               ` Linus Torvalds
2005-04-16  4:10                                                 ` Junio C Hamano
2005-04-16  5:02                                                   ` Linus Torvalds
2005-04-16  6:26                                                     ` Linus Torvalds
2005-04-16  8:12                                                     ` Junio C Hamano
2005-04-16  9:27                                                       ` [PATCH] Byteorder fix for read-tree, new -m semantics version Junio C Hamano
2005-04-16 10:35                                                       ` [PATCH 1/2] Add --stage to show-files for new stage dircache Junio C Hamano
2005-04-16 10:42                                                         ` [PATCH 2/2] " Junio C Hamano
2005-04-16 14:03                                                       ` Issues with higher-order stages in " Junio C Hamano
2005-04-17  5:11                                                         ` Junio C Hamano
2005-04-17  5:31                                                           ` Linus Torvalds
2005-04-17  6:01                                                             ` Junio C Hamano
2005-04-17 10:00                                                         ` Summary of "read-tree -m O A B" mechanism Junio C Hamano
2005-04-16 15:28                                                       ` [PATCH 3/2] merge-trees script for Linus git Linus Torvalds
2005-04-16 16:36                                                         ` Linus Torvalds
2005-04-16 17:14                                                           ` Junio C Hamano
2005-04-15 19:54                             ` Re: Merge with git-pasky II Petr Baudis
2005-04-15 10:22                           ` Junio C Hamano
2005-04-15 20:40                             ` Petr Baudis
2005-04-15 22:41                               ` Junio C Hamano
2005-04-15 19:57           ` Junio C Hamano
2005-04-15 20:45             ` Linus Torvalds
2005-04-14  0:30 ` Petr Baudis
2005-04-14 22:11 ` git merge Petr Baudis
     [not found] <000d01c541ed$32241fd0$6400a8c0@gandalf>
2005-04-15 20:31 ` Merge with git-pasky II Linus Torvalds
2005-04-15 23:00   ` Barry Silverman
2005-04-16  0:32     ` Linus Torvalds
2005-04-26 18:55 Bram Cohen
2005-04-26 19:58 ` Linus Torvalds
2005-04-26 20:30   ` Tom Lord
2005-04-26 20:31   ` Bram Cohen
2005-04-26 20:39     ` Tom Lord
2005-04-26 20:58     ` Linus Torvalds
2005-04-26 21:25       ` Linus Torvalds
2005-04-26 21:28       ` Bram Cohen
2005-04-26 21:36         ` Fabian Franz
2005-04-26 22:30           ` Linus Torvalds
2005-04-26 22:25         ` Linus Torvalds
2005-04-28  0:42           ` Petr Baudis
2005-04-26 21:26     ` Diego Calleja
2005-04-26 20:31   ` Daniel Barkalow
2005-04-26 20:44     ` Tom Lord

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply to all the recipients using the --to, --cc,
  and --in-reply-to switches of git-send-email(1):

  git send-email \
    --in-reply-to=Pine.LNX.4.58.0504150753440.7211@ppc970.osdl.org \
    --to=torvalds@osdl.org \
    --cc=dwmw2@infradead.org \
    --cc=git@vger.kernel.org \
    --cc=junkio@cox.net \
    --cc=pasky@ucw.cz \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

git@vger.kernel.org mailing list mirror (one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/
       or Tor2web: https://www.tor2web.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox