* [PATCH] trivial argument parsing patches
From: Paul Mackerras @ 2005-04-15 11:28 UTC (permalink / raw)
To: git
In perusing the git code, I noticed some errors in argument parsing,
which the patch below fixes. The show-diff error (checking argv[1]
each time around the loop) probably doesn't actually cause any real
problem, but it could be confusing for a novice if "show-diff x"
produces an error but "show-diff -s x" doesn't (and ignores the extra
argument).
Signed-off-by: Paul Mackerras <paulus@samba.org>
rev-tree.c: 7bf9e9a92f528485360f374239809714ce7a19f5
--- rev-tree.c
+++ rev-tree.c 2005-04-15 21:17:16.000000000 +1000
@@ -189,8 +189,8 @@
char *arg = argv[i];
if (!strcmp(arg, "--cache")) {
- read_cache_file(argv[2]);
i++;
+ read_cache_file(argv[i]);
continue;
}
show-diff.c: a531ca4078525d1c8dcf84aae0bfa89fed6e5d96
--- show-diff.c
+++ show-diff.c 2005-04-15 21:22:28.000000000 +1000
@@ -61,12 +61,10 @@
int entries = read_cache();
int i;
- while (argc-- > 1) {
- if (!strcmp(argv[1], "-s")) {
- silent = 1;
- continue;
- }
- usage("show-diff [-s]");
+ if (argc > 1) {
+ if (argc > 2 || strcmp(argv[1], "-s"))
+ usage("show-diff [-s]");
+ silent = 1;
}
if (entries < 0) {
^ permalink raw reply
* Re: Git archive now available
From: Darren Williams @ 2005-04-15 12:00 UTC (permalink / raw)
To: Git Mailing List, LKML; +Cc: Kenneth Johansson
In-Reply-To: <20050415000147.GA1480@cse.unsw.EDU.AU>
On Fri, 15 Apr 2005, Darren Williams wrote:
> Hi All
>
> Thanks to the team at Gelato@UNSW we now have a
> no so complete Git archive at
> http://www.gelato.unsw.edu.au/archives/git/
>
> If somebody could send me a complete Git mbox I will
> update the archive with it.
Apparently gmane.org have archived the list here is
the link.
http://dir.gmane.org/gmane.comp.version-control.git
Sorry Kenneth for the previous spam.
- dsw
>
> - dsw
>
> --------------------------------------------------
> Darren Williams <dsw AT gelato.unsw.edu.au>
> Gelato@UNSW <www.gelato.unsw.edu.au>
> --------------------------------------------------
> -
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
--------------------------------------------------
Darren Williams <dsw AT gelato.unsw.edu.au>
Gelato@UNSW <www.gelato.unsw.edu.au>
--------------------------------------------------
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Johannes Schindelin @ 2005-04-15 12:03 UTC (permalink / raw)
To: David Woodhouse; +Cc: Linus Torvalds, Junio C Hamano, Petr Baudis, git
In-Reply-To: <1113556448.12012.269.camel@baythorne.infradead.org>
Hi,
On Fri, 15 Apr 2005, David Woodhouse wrote:
> On Thu, 2005-04-14 at 11:36 -0700, Linus Torvalds wrote:
> > And "merge these two trees" (which works on a _tree_ level)
> > or "find the common commit" (which works on a _commit_ level)
>
> I suspect that finding the common commit is actually a per-file thing;
> it's not just something you do for the _commit_ graph, then use for
> merging each file in the two branches you're trying to merge.
I disagree. In order to be trusted, this thing has to catch the following
scenario:
Skywalker and Solo start from the same base. They commit quite a lot to
their trees. In between, Skywalker commits a tree, where the function
"kazoom()" has been added to the file "deathstar.c", but Solo also added
this function, but to the file "moon.c". A file-based merge would have no
problem merging each file, such that in the end, "kazoom()" is defined
twice.
The same problems arise when one tries to merge line-wise, i.e. when for
each line a (possibly different) merge-parent is sought.
The concept here is a *transaction*: when going from one tree to the next
tree via a commit, a sort of integrity is maintained, which is breached
when only looking at files and commits.
Ciao,
Dscho
^ permalink raw reply
* Re: Handling renames.
From: linux @ 2005-04-15 13:37 UTC (permalink / raw)
To: dwmw2; +Cc: git
> One option for optimising this, if we really need to, might be to track
> the file back to its _first_ ancestor and use that as an identification.
> The SCM could store that identifier in the blob itself, or we could
> consider it an 'inode number' and store it in git's tree objects.
This suggestion (and this whole discussion about renames) has issues
with file copies, which form a branch in the revision history. If I
copy foo.c to foo2.c (or fs/ext2/ to fs/ext3/), then the oldest ancestor
isn't a "unique inode number".
I've written a lot of programs by debugging hello.c.
Thinking about this can give you all sorts of exciting merge possibilities.
If branch1 renames a.c to b.c, and branch2 patches a.c, it seems obvious
that the patch should be merged into b.c. But what if branch1 copies a.c
to b.c?
^ permalink raw reply
* Re: Handling renames.
From: David Woodhouse @ 2005-04-15 13:53 UTC (permalink / raw)
To: linux; +Cc: git
In-Reply-To: <20050415133759.7560.qmail@science.horizon.com>
On Fri, 2005-04-15 at 13:37 +0000, linux@horizon.com wrote:
> > One option for optimising this, if we really need to, might be to track
> > the file back to its _first_ ancestor and use that as an identification.
> > The SCM could store that identifier in the blob itself, or we could
> > consider it an 'inode number' and store it in git's tree objects.
>
> This suggestion (and this whole discussion about renames) has issues
> with file copies, which form a branch in the revision history. If I
> copy foo.c to foo2.c (or fs/ext2/ to fs/ext3/), then the oldest ancestor
> isn't a "unique inode number".
That's why I prefer the option of simply annotating the moves. They
don't need to be just renames -- it can cover the cases where files are
split up or merged into one, to indicate where the history of the given
_data_ is coming from.
--
dwmw2
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Theodore Ts'o @ 2005-04-15 10:22 UTC (permalink / raw)
To: Johannes Schindelin
Cc: David Woodhouse, Linus Torvalds, Junio C Hamano, Petr Baudis, git
In-Reply-To: <Pine.LNX.4.58.0504151340221.27162@wgmdd8.biozentrum.uni-wuerzburg.de>
On Fri, Apr 15, 2005 at 02:03:08PM +0200, Johannes Schindelin wrote:
> I disagree. In order to be trusted, this thing has to catch the following
> scenario:
>
> Skywalker and Solo start from the same base. They commit quite a lot to
> their trees. In between, Skywalker commits a tree, where the function
> "kazoom()" has been added to the file "deathstar.c", but Solo also added
> this function, but to the file "moon.c". A file-based merge would have no
> problem merging each file, such that in the end, "kazoom()" is defined
> twice.
>
> The same problems arise when one tries to merge line-wise, i.e. when for
> each line a (possibly different) merge-parent is sought.
Be careful. There is a very big tradeoff between 100% perfections in
catching these sorts of errors, and usability. There exists SCM's
where you are not allowed to do commit such merges until you do a test
compile, or run a regression test suite (that being the only way to
catch these sorts of problems when we merge two branches like this).
BitKeeper never caught this sort of thing, and we trusted it. In
practice it was also rarely a problem.
I'll also note that BitKeeper doesn't restrict you from doing a
committing a changeset when you have modified files that have yet to
be checked in to the tree. Same issue; you can accidentally check in
changesets that in trees that won't build, but if we added this kind
of SCM-by-straightjacket philosophy it would decrease our productivity
and people would simply not use such an SCM, thus negating its
effectiveness.
- Ted
^ permalink raw reply
* Re: another perspective on renames.
From: C. Scott Ananian @ 2005-04-15 14:47 UTC (permalink / raw)
To: Paul Jackson; +Cc: git
In-Reply-To: <20050414221626.10c6c0e7.pj@engr.sgi.com>
On Thu, 14 Apr 2005, Paul Jackson wrote:
> To me, rename is a special case of the more general case of a
> big chunk of code (a portion of a file) that was in one place
> either being moved or copied to another place.
>
> I wonder if there might be someway to use the tools that biologists use
> to analyze DNA sequences, to track the evolution of source code,
> identifying things like common chunks of code that differ in just a few
> mutations, and presenting the history of the evolution, at selectable
> levels of detail.
The rsync algorithm (http://samba.anu.edu.au/rsync/tech_report/node2.html)
is probably a good place to start, although it is relatively sensitive to
mutations. It will be able to efficiently detect identical blocks larger
than some block size N (512 bytes or so for rsync). You might well
consider smaller blocks to be irrelevant. The data can be made
considerably more useful to developers by canonicalizing before searching
(ie, compressing whitespace to ' ', etc)[*]. Note that the identical
regions do *not* have to line up on block boundaries; see the rsync
algorithm for more detail.
I think Linus has made a persuasive case that the 'developer-friendly'
features of an SCM (ie annotate, log, and friends) can be built *on top*
of GIT. This is a perfect example. Since the computation is non-trivial
(although linear in the number of lines of code involved in the history of
a file; ie doesn't depend on the unrelated size of the archive), it might
make sense for the front-end SCM to maintain its own caches --- for
example, of the block and rolling checksums for each file required by the
rsync algorithm. The key point being that these are just *caches*, not
essential history information, and can always be wiped and regenerated.
The nice 'feature' of this system (some may disagree, I guess) is that it
does *not* depend on extensive programmer annotation of file changes (ie,
chunk A in file B came from lines C-D of file D, or file E was once named
F, etc). By inferring history from content-similar files and blocks, it
seems that it would be more able to generate useful results after
importing third-party sources, which may come in distinct 'releases' but
lack explicit history annotations.
--scott
[*] in general, i will be *glad* to see source-management move away from
CVS' line-oriented style; there's no good reason we should still be worrying
about whitespace changes, etc. When we build 'developer-friendly' tools
we should make every effort to auto-detect source code, image formats,
etc, and automatically perform appropriate canonicalization and
beautification of diffs, because this can be/should be/is entirely
separate from git's underlying storage representation.
Mk 48 PANCHO ZPSECANT MKDELTA SCRANTON D5 SLBM JMTRAX Delta Force
MI6 SGUAT Khaddafi SMOTH interception mail drop SECANT PBSUCCESS Cocaine
( http://cscott.net/ )
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Linus Torvalds @ 2005-04-15 14:53 UTC (permalink / raw)
To: David Woodhouse; +Cc: Junio C Hamano, Petr Baudis, git
In-Reply-To: <1113556448.12012.269.camel@baythorne.infradead.org>
On Fri, 15 Apr 2005, David Woodhouse wrote:
>
> I suspect that finding the common commit is actually a per-file thing;
> it's not just something you do for the _commit_ graph, then use for
> merging each file in the two branches you're trying to merge.
I disagree.
Conceptually, you should never do _anything_ on a file level. Why? Because
individual files don't matter. You shouldn't merge two files cleanly just
because they look fine - they _depend_ on the other files in the archive,
and that's quite fundamentally why per-file tracking is really wrong from
a project standpoint.
So if you can't merge two files cleanly because the "project" history
ended up being further back than the "file" history, then that's a _good_
thing. You don't know what the hell happened to the other files that this
file depended on. Merging one file independently of the others is WRONG.
Also, I suspect that you'll find that if you do cross-merges, you'll
basically always end up in:
> (I think it's a coincidence that in my example the useful files 'A2' and
> 'B2' actually do end up in a single tree together at some point.)
nope, I don't think that's coincidence. I think that's the normal case.
Your file-based history is the one that can _incorrectly_ and
coincidentally happen to have a single file at some point, but since that
file doesn't stand alone, that's really not a fundamentally good reason to
merge it.
Really, this "individual files matter" approach is a _disease_. They
don't. Individual files DO NOT EXIST. Files always exist as part of the
project, and the _only_ time you track a single file is when the project
is a single file (and then that will be very very obvious in a git
archive, thank you very much).
So the single-file mentality is a disease brought on by decades of _crap_.
And by the fact that it ends up limiting the problem scope, so you can do
certain things easier.
For example, just doing intra-file diffs is a lot _easier_ and less
time-consuming than doing inter-file diffs. Bit it is _absolutely_ not
better. In fact, it is clearly inferior to anybody who spends even five
seconds thinking about it - yet we still do it, because of the historical
(and INCORRECT) mindset that "files matter".
Files DO NOT matter. Never have. It's an implementation limitation to
think they do. You'll screw yourself up, and when somebody comes up with a
half-way efficient way to generate inter-fiel diffs, your architecture is
totally and utterly unable to handle it.
I don't care what you do at an SCM level, and if the crud you put on top
of git wants to perpetuate mistakes of yesteryear, that's _your_ issue.
But dammit, git is designed to do the right thing, and I will fight tooth
and nail against anybody who thinks individual files matter.
Linus
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Ingo Molnar @ 2005-04-15 14:53 UTC (permalink / raw)
To: David Woodhouse; +Cc: Linus Torvalds, Junio C Hamano, Petr Baudis, git
In-Reply-To: <1113559533.12012.296.camel@baythorne.infradead.org>
* David Woodhouse <dwmw2@infradead.org> wrote:
> On Fri, 2005-04-15 at 11:36 +0200, Ingo Molnar wrote:
> > do such cases occur frequently? In the kernel at least it's not too
> > typical.
>
> Isn't it? I thought it was a fairly accurate representation of the
> process "I make a whole bunch of changes to files I maintain, pulling
> from Linus while occasionally asking him to pull from my tree.
> Sometimes my files are changed by someone else in Linus' tree, and
> sometimes I change files that I don't actually own.".
but the specific scenario you described would require _Linus'_ tree to
be in limbo for a long time, and have uncommitted half-done edits. I.e.:
(A1B2)--(A2B2)--(A2'B3)
/ \ / \
/ \ / \
(A1B1) X (...)
\ / \ /
\ / \ /
(A2B1)--(A2B2)--(A3B2')
in the above scenario Linus' tree needs to 'cross' with a maintainer's
tree. (maintainer's tree wont cross with another maintainer's tree, as
maintainer-to-maintainer merges rare.)
but for the scenario to occur, i think there needs to be a prolongued
"limbo" period in Linus' tree for a 'crossing' to happen. But Linus'
merges are typically almost atomic: they are done then they are pushed
out. It's definitely not in the 'days, sometimes weeks' timescale as
maintainer trees are.
so for the scenario to occur, a maintainer, from whom Linus has just
pulled an update and Linus is merging the tree manually without
comitting, has to pull a file from the earlier Linus tree, and then
Linus has to modify that same file again. This does not seem to be a
common scenario.
so i think to avoid the scenario, maintainers should not pull from each
other - they should only pull/push to/from Linus' tree. Maybe this is an
unacceptable limitation?
Ingo
^ permalink raw reply
* Re: Merge with git-pasky II.
From: David Woodhouse @ 2005-04-15 15:09 UTC (permalink / raw)
To: Ingo Molnar; +Cc: Linus Torvalds, Junio C Hamano, Petr Baudis, git
In-Reply-To: <20050415145324.GA4677@elte.hu>
On Fri, 2005-04-15 at 16:53 +0200, Ingo Molnar wrote:
> but the specific scenario you described would require _Linus'_ tree to
> be in limbo for a long time, and have uncommitted half-done edits.
> I.e.:
>
> (A1B2)--(A2B2)--(A2'B3)
> / \ / \
> / \ / \
> (A1B1) X (...)
> \ / \ /
> \ / \ /
> (A2B1)--(A2B2)--(A3B2')
>
> in the above scenario Linus' tree needs to 'cross' with a maintainer's
> tree. (maintainer's tree wont cross with another maintainer's tree,
> as maintainer-to-maintainer merges rare.)
Is that true? Consider (A2B1) to be a bugfixes-only tree which I make
available for Linus to pull from. I keep doing more experimental stuff
in my own private copy of the tree along the bottom branch, while Linus
_eventually_ responds to my pull request and moves on, stopping only to
add a 'static' to one of my new functions. I move on too but don't pull
from Linus again for a little while; the final merge happens when I _do_
pull again.
--
dwmw2
^ permalink raw reply
* Re: Merge with git-pasky II.
From: David Woodhouse @ 2005-04-15 15:29 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, Petr Baudis, git
In-Reply-To: <Pine.LNX.4.58.0504150740310.7211@ppc970.osdl.org>
On Fri, 2005-04-15 at 07:53 -0700, Linus Torvalds wrote:
> Files DO NOT matter. Never have. It's an implementation limitation to
> think they do. You'll screw yourself up, and when somebody comes up with a
> half-way efficient way to generate inter-fiel diffs, your architecture is
> totally and utterly unable to handle it.
>
> I don't care what you do at an SCM level, and if the crud you put on top
> of git wants to perpetuate mistakes of yesteryear, that's _your_ issue.
> But dammit, git is designed to do the right thing, and I will fight tooth
> and nail against anybody who thinks individual files matter.
No, really: individual files _DO_ matter. There's a reason we split
stuff up into separate files, and if you look closely you'll find that
we don't just randomly put different functions into different files with
neither rhyme nor reason -- there's a pattern to it; usually some kind
of functional grouping.
And when I'm looking for the change that broke something, I can almost
always tell which file it's in and go looking in _that_ file. It's a
_whole_ lot easier to use the equivalent of 'bk revtool' than it is to
sift through all the unrelated commits in the whole tree. If that's an
implementation limitation, then it's an implementation limitation in my
_brain_ not just in my tools.
OK, in fact it shouldn't be 'show me the history of this file'; it's
often really 'show me the history of this function' which I want. But
that's fine. All I'm suggesting is that we should include the metadata
which says "content moved from file XXX to file YYY" along with the
commit objects.
I'm certainly not suggesting that we should implement jejb's idea of
explicit 'file revision history' objects -- the tree-based philosophy is
perfectly sane and sufficient. But we do _also_ need a little
information which allows us to track content as it moves around within
the tree, and the SCM has to have a sane way to filter out the noise
when we're looking for what broke. Yes, that's part of the SCM
functionality, and can live in an xattr-type field in the commit object
-- but it does need to be stored, and in practice I suspect it _will_ be
useful for merging too.
It's not about ditching the per-tree tracking and doing per-file
tracking instead. I agree that would be wrong. It's about storing enough
information to track what happened to given content as it moved around
within the tree.
--
dwmw2
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Linus Torvalds @ 2005-04-15 15:32 UTC (permalink / raw)
To: David Woodhouse; +Cc: Junio C Hamano, Petr Baudis, git
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
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Linus Torvalds @ 2005-04-15 15:51 UTC (permalink / raw)
To: David Woodhouse; +Cc: Junio C Hamano, Petr Baudis, git
In-Reply-To: <1113578964.27227.65.camel@hades.cambridge.redhat.com>
On Fri, 15 Apr 2005, David Woodhouse wrote:
>
> And when I'm looking for the change that broke something, I can almost
> always tell which file it's in and go looking in _that_ file.
Read my email about finding "what changed" that I sent out a minute ago.
I claim that my algorithm for finding "what changed" handles your "single
file" case as a very small (and usually quite uninteresting) special case.
I claim (and if you just look at my proposal I think you'll agree) that I
can track single functions, and do it efficiently. WITHOUT adding any
meta-data at all.
The thing is, if the question is "I have this piece of code, and I want to
see what changed", you fundamentally _can_ do that efficiently. That's
really what git was designed for. It's the whole _point_ of having history
in the first place. If git didn't care, it wouldn't have a back-pointer to
the tree it came from, and we'd all be just merging pure trees.
But you mix that question up with "how do I save that information in the
commit", which is a totally unnecessary mix-up, and which makes things
MUCH more complicated, for absolutely zero gain.
In fact, because you mixed up those two issues, the problem now became so
complicated that you can no longer solve it, so you start doing hacks like
"the user has to tell us what he did" (aka "bk mv" or "svn rename"), and
you start mentally to limit yourself to files, because you realize that
you _have_ to limit your intractable problem to make it at all solvable.
And I'm telling you that your problem is STUPID. You made it stupid by
thinking that every question about the source tree should be answered at
commit time. Which just clearly isn't true!
If you just drop the tying-together, and accept that "what changed" is a
valid question _regardless_ of trying to track it at commit time, now your
whole world opens up. Birds sing, the sun is shining on you, and beautiful
scantily clad women (or men) dance around you. The world is suddenly a
good place, just _filled_ with possibilities.
Suddenly you realize that if the question is just "what changed in this
piece of code" (and let's face it, that _is_ the question), you can track
it afterwards. Trying to tie in "commit time" into the question was what
made it hard. If you do _not_ due that (totally unnecessary) tie-in, the
question suddenly becomes easy to answer, and several obvious and simple
answers spring to mind pretty immediately.
> It's not about ditching the per-tree tracking and doing per-file
> tracking instead. I agree that would be wrong. It's about storing enough
> information to track what happened to given content as it moved around
> within the tree.
No. Git absolutely does have everything you need already. You just aren't
realizing that it's already there - in the data - and that you can do much
more intelligent searches for changes if you accept that undeniable fact.
The fact that you can NOT do those searches at commit-time (which is a
global op), and can only do them if you have a specific question in mind
("what changed _here_"), is the big issue.
The thing is, at commit-time you'd need to answer every possible question
("what changed here, and here, and here, and in this function, and in this
file, and in this directory and why did this identifier get renamed and
why is the sky blue"). AND YOU FUNDAMENTALLY CANNOT DO THAT. It's
impossible.
But once you _know_ the question (which is the only time when the answer
is actually relevant, so why care about if before that time?), you can
find out the answer by just automating the job of looking at the _data_.
It's easy. The question makes it obvious by its nature. The question is
the thing that gives you the specifics that makes the search possible in
the first place.
And _this_ is why the data matters. Renames and file boundaries do not.
And until you accept that, you just limit yourself.
Linus
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Paul Jackson @ 2005-04-15 15:54 UTC (permalink / raw)
To: Linus Torvalds; +Cc: dwmw2, junkio, pasky, git
In-Reply-To: <Pine.LNX.4.58.0504150740310.7211@ppc970.osdl.org>
Linus wrote:
> For example, just doing intra-file diffs is a lot _easier_ and less
> time-consuming than doing inter-file diffs.
Um ah ... could you explain what you mean by inter and intra file diffs?
Google found a three year old message by Andrew Morton, discussing
inter and intra file fragmentation on ext2/ext3 file systems and the
find_group_dir() routine. I don't think that's what you had in mind ;).
When I run the 'diff' command, it usually between two files, not between
two parts of a file. So I'd have thought inter file diffs were easier.
Clearly, I don't git it.
--
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <pj@engr.sgi.com> 1.650.933.1373, 1.925.600.0401
^ permalink raw reply
* Re: Merge with git-pasky II.
From: David Woodhouse @ 2005-04-15 16:01 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, Petr Baudis, git
In-Reply-To: <Pine.LNX.4.58.0504150753440.7211@ppc970.osdl.org>
On Fri, 2005-04-15 at 08:32 -0700, Linus Torvalds wrote:
> - 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".
OK, I'm inclined to agree. The only thing that prevents me from
capitulating entirely and resubscribing to the "Torvalds is always
right" school is the concern that it _is_ expensive, and that's why I
originally wanted to do it at commit time because then it's a one-off
cost rather than recurring every time we want to track the history of a
given piece of content. Also because we actually have the developer's
attention at commit time, and we can get _real_ answers from the user
about what she was doing, instead of having to guess.
But if it can be done cheaply enough at a later date even though we end
up repeating ourselves, and if it can be done _well_ enough that we
shouldn't have just asked the user in the first place, then yes, OK I
agree.
--
dwmw2
^ permalink raw reply
* Re: ls-tree enhancements
From: Petr Baudis @ 2005-04-15 16:13 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, git
In-Reply-To: <7vzmw0ok45.fsf_-_@assigned-by-dhcp.cox.net>
Dear diary, on Fri, Apr 15, 2005 at 04:21:30AM CEST, I got a letter
where Junio C Hamano <junkio@cox.net> told me that...
> +static void _usage(void)
> +{
> + usage("ls-tree [-r] [-z] <key>");
> +}
(namespace-nazi-hat
This infriges the system namespaces. FWIW, I prefer to add the
underscore at the end of the identifier if wanting to do stuff like
this. Or just call it my_usage().
)
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Out-tree merges
From: Petr Baudis @ 2005-04-15 16:29 UTC (permalink / raw)
To: torvalds; +Cc: git
Hello,
I've been thinking about it, and although it seemed Just Sensible
initially, I'm liking it less and less now that I'm actually doing
out-tree merges (git merge already supports it). What is the motivation
of doing things outside of your working directory?
The only one I can imagine is that it could interfere with some local
changes in your directory. And I think that this does not make sense.
Either you are going to keep them and you should commit them, or you
don't and there's no reason for keeping them around. Is this really that
common for you?
I have two counter-arguments. First, you likely can't build the thing
in your merge tree, so you can't check if it even compiles after the
merge went through. Second, you need to work quite differently when
working in a merge tree. You can't grep for stuff, you cannot (without
thinking about it and going to different directories) peek to header
files to check if this structure member is really __u32, etc. You might
do all of this when merging, let's say when solving weird conflicts.
Of course being better off with your working directory assumes that
you have one. OTOH it is hardly imaginable for me that you would all of
sudden want to say "hey, now I want to take these two trees all of
sudden and void and merge them together". Not in any common real world
cases. Or am I wrong?
So, I'm thinking whether to just revert to the original behaviour of
doing the merges in the working tree, or make it optional (which would
make the scripts more complicated and convoluted).
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: Merge with git-pasky II.
From: C. Scott Ananian @ 2005-04-15 16:30 UTC (permalink / raw)
To: Paul Jackson; +Cc: Linus Torvalds, dwmw2, junkio, pasky, git
In-Reply-To: <20050415085424.5f61b80b.pj@engr.sgi.com>
On Fri, 15 Apr 2005, Paul Jackson wrote:
> Um ah ... could you explain what you mean by inter and intra file diffs?
intra file diffs: here are two versions of the same file. what changed?
inter file diffs: here is a new file, and here are *all the files in the
current committed version*. Where did the contents of this new file come
from? (Note that the new file is often a slightly changed version of an
existing file in the current committed version. But we don't assume that
must be true.)
--scott
supercomputer Pakistan WSHOOFS SECANT LCPANGS SDI assassination ZPSECANT
SEQUIN AEBARMAN ESCOBILLA bomb mustard STANDEL ESGAIN Nazi FJDEFLECT
( http://cscott.net/ )
^ permalink raw reply
* Re: Merge with git-pasky II.
From: C. Scott Ananian @ 2005-04-15 16:31 UTC (permalink / raw)
To: David Woodhouse; +Cc: Linus Torvalds, Junio C Hamano, Petr Baudis, git
In-Reply-To: <1113580881.27227.73.camel@hades.cambridge.redhat.com>
On Fri, 15 Apr 2005, David Woodhouse wrote:
> given piece of content. Also because we actually have the developer's
> attention at commit time, and we can get _real_ answers from the user
> about what she was doing, instead of having to guess.
Yes, but it's still hard to get *accurate* information. And developers
tend to use very short commit messages already...
> But if it can be done cheaply enough at a later date even though we end
> up repeating ourselves, and if it can be done _well_ enough that we
> shouldn't have just asked the user in the first place, then yes, OK I
> agree.
I think examining the rsync algorithms should convince you that finding
common chunks can be fairly efficient. (See my next message for a more
concrete proposal.)
--scott
Rijndael AMLASH Moscow Ft. Bragg shotgun HTKEEPER SHERWOOD overthrow
Uzi anthrax Yeltsin Indonesia Suharto LITEMPO Dictionary Yakima KUBARK
( http://cscott.net/ )
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Linus Torvalds @ 2005-04-15 17:11 UTC (permalink / raw)
To: C. Scott Ananian; +Cc: David Woodhouse, Junio C Hamano, Petr Baudis, git
In-Reply-To: <Pine.LNX.4.61.0504151230180.27637@cag.csail.mit.edu>
On Fri, 15 Apr 2005, C. Scott Ananian wrote:
>
> I think examining the rsync algorithms should convince you that finding
> common chunks can be fairly efficient.
Note that "efficient" really depends on how good a job you want to do, so
you can tune it to how much CPU you can afford to waste on the problem.
For example, my example had this thing where we merged five different
functions into one function, and it is truly pretty efficient to find
things like that _IF_ we only look at the files that changed (since the
set of files that change in any one particular commit tends to be small,
relative to the whole repository). There are many good algorithms for
finding "common code", and with modern hardware that is basically
instantaneous if you look at a few tens of files.
For example, people wrote efficient things to compare _millions_ of lines
of code for the whole SCO saga - you can do quite well. Some googling
comes up with for example
http://minnie.tuhs.org/Programs
and applying those to a smallish set of files is quite efficient.
What is _not_ necessarily as easy is the situation where you notice that a
new set of lines appeared, but you don't see any place that matches that
set of lines in the set of CHANGED files. That's actually quite common, ie
let's say that you have a new filesystem or a new driver, and almost
always it's based on a template or something, and you _would_ be able to
see where that template came from, except it's not in that _changed_ set.
And that is still doable, but now you really have to compare against the
whole tree if you want to do it. Even _that_ is actually efficient if you
cache the hashes - that's how the comparison tools compare two totally
independent trees against each other, and it makes it practically possible
to do even that expensive O(n**2) operation in reasonable time. It's
certainly possible to do exactly the same thing for the "new code got
added, does it bear any similarity to old code" case.
Note! This is a question that is relevant and actually is in the realm of
the "possible to find the answer interactively". It may fairly expensive,
but the point is that this is the kind of relevant question that really
does depend on the fundamental notion that "data matters more than any
local changes". And when you think about the problem in that form, you
find these kinds of interesting questions that you _can_ answer.
Because the way git identifies data, the example "is there any other
relevant code that may actually be similar to the newly added code" is
actually not that hard to do in git. Remember: the way to answer that
question is to have a cache of hashes of the contents. Guess what git
_is_? You can now index your line-based hashes of contents against the
_object_ hashes that git keeps track of, and you suddenly have an
efficient way to actually look up those hashes.
NOTE! All of this is outside the scope of git itself. This is all
"visualization and comparison tools" built up on top of git. And I'm not
at all interested in writing those tools myself, and I'm absolutely not
signing up for that part. All I'm arguing for is that the git architecture
is actually a very good architecture for doing these kinds of very very
cool tools.
Linus
^ permalink raw reply
* space compression (again)
From: C. Scott Ananian @ 2005-04-15 17:19 UTC (permalink / raw)
To: git
I've been reading the archives (a bad idea, I know). Here's a concrete
suggestion for GIT space-compression which is (I believe) consistent with
the philosophy of GIT.
Why are blobs per-file? [After all, Linus insists that files are an
illusion.] Why not just have 'chunks', and assemble *these*
into blobs (read, 'files')? A good chunk size would fit evenly into some
number of disk blocks (no wasted space!).
We already have the rsync algorithm which can scan through a file and
efficiently tell which existing chunks match (portions of) it, using a
rolling checksum. (Here's a refresher:
http://samba.anu.edu.au/rsync/tech_report/node2.html
). Why not treat the 'chunk' as the fundamental unit, and compose files
from chunks?
This should get better space utilization: a small change to file X
will only require storage to save the changed chunk, plus meta data to
describe the chunks composing the new file. I propose keeping this only
one-level deep: we can only specify chunks, not pieces of files.
Unlike xdelta schemes, there is no 'file' dependency. Chunks for a blob
can be and are shared among *all the other files and versions in the
repository*. Moving pieces from file 'a' to file 'b' "just works".
Best of all, I believe this can be done in a completely layered fashion.
From git's perspective, it's still 'open this blob' or 'write this blob'.
It just turns out that the filesystem representation of a blob is slightly
more fragmented. Even better, you ought to be able to convert your
on-disk store from one representation to the other: the named blob doesn't
change, just 'how to fetch the blob' changes. So, for example, Linus'
tree can be unchunked for speed, but the release tree (say) can pull
pruned history from Linus into a chunked on-disk representation that can
be efficiently wget'ted (only new chunks need be transferred).
My first concern is possible fragmentation: would we end up with a large
number of very small chunks, and end up representing files as a list of
lines (effectively)? Maybe someone can think of an effective coalescing
strategy, or maybe it is sufficient just to avoid creating chunks smaller
than a certain size (ie, possibly writing redundant data to a new chunk,
just to improve the possibility of reuse).
I'm also not sure what the best 'chunk' size is. Smaller chunks save more
space but cost more to access (# of disk seeks per file/blob). Picking a
chunk half the average file size should reduce space by ~50% while only
requiring ~2 additional seeks per file-read. OTOH, rsync experience
suggests 500-1000 byte chunk sizes. Probably empirical testing is best.
Lastly, we want to avoid hitting the dcache to check the existence of
chunks while encoding. In a large repository, there will be a very large
number of chunks. We don't *have* to index all of them, but our
compression gets better the more chunks we know about. The rsync
algorithm creates hash tables of chunks at different levels of granularity
to avoid doing a full check at every byte of the input file. How large
should this cached-on-disk chunk hash table be to avoid saturating it as
the repository grows (maybe the standard grow-as-you-go hash table is
fine; you only need one bit per entry anyway)?
Thoughts? Is the constant-factor overhead of indirection-per-blob going
to kill git's overwhelming speed?
--scott
JUBILIST explosion MKULTRA HTAUTOMAT Indonesia Shoal Bay RUCKUS ammunition
GPFLOOR Hager SDI MKDELTA KUBARK Dictionary Soviet BLUEBIRD Delta Force
( http://cscott.net/ )
^ permalink raw reply
* Re: fix various issues in gitapply.sh (basically did not handle add/del/cm at all)
From: Petr Baudis @ 2005-04-15 18:15 UTC (permalink / raw)
To: Martin Schlemmer; +Cc: GIT Mailing Lists
In-Reply-To: <1113557318.23299.165.camel@nosferatu.lan>
Dear diary, on Fri, Apr 15, 2005 at 11:28:38AM CEST, I got a letter
where Martin Schlemmer <azarah@nosferatu.za.org> told me that...
> Hi,
>
> The egrep regex should not escape the '{' and '}', and also add a check
> for ' \t' so that we do not pickup stuff like '+----', etc. Fix typo in
> assignment. Check if file exists in new tree before adding/removing
> (might add support for this lowlevel to increase speed?). Fix typo in
> line removing temp files.
>
> Signed-off-by: Martin Schlemmer <azarah@gentoo.org>
Thanks for the merge and typo fixes. I can't imagine how, but it really
appeared to work for me that time!
I'm confused however what does the exits_in_cache() (what exits? exists?)
gives us, apart of horribly-looking code. What bug does it fix?
Thanks,
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: ls-tree enhancements
From: Junio C Hamano @ 2005-04-15 18:25 UTC (permalink / raw)
To: Petr Baudis; +Cc: Linus Torvalds, git
In-Reply-To: <20050415161330.GH19078@pasky.ji.cz>
>>>>> "PB" == Petr Baudis <pasky@ucw.cz> writes:
>> +static void _usage(void)
PB> This infriges the system namespaces. FWIW, I prefer to add the
PB> underscore at the end of the identifier if wanting to do stuff like
PB> this. Or just call it my_usage().
Thanks. My bad. Noted.
^ permalink raw reply
* Re: Merge with git-pasky II.
From: Paul Jackson @ 2005-04-15 18:29 UTC (permalink / raw)
To: C. Scott Ananian; +Cc: torvalds, dwmw2, junkio, pasky, git
In-Reply-To: <Pine.LNX.4.61.0504151227590.27637@cag.csail.mit.edu>
> intra file diffs: here are two versions of the same file.
Ah so. Linus faked me out.
I was _sure_ that by "file" he meant "file" -- as in a bucket of bits
with a unique identifying <sha1>.
In that message, I guess by "file" he meant "a version controlled
file, consisting of a series of content versions and meta-data"
That's what I get for trusting Linus to always speak as a kernel
hacker, not an SCM hacker.
--
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <pj@engr.sgi.com> 1.650.933.1373, 1.925.600.0401
^ permalink raw reply
* Re: space compression (again)
From: Linus Torvalds @ 2005-04-15 18:34 UTC (permalink / raw)
To: C. Scott Ananian; +Cc: git
In-Reply-To: <Pine.LNX.4.61.0504151232160.27637@cag.csail.mit.edu>
On Fri, 15 Apr 2005, C. Scott Ananian wrote:
>
> Why are blobs per-file? [After all, Linus insists that files are an
> illusion.] Why not just have 'chunks', and assemble *these*
> into blobs (read, 'files')? A good chunk size would fit evenly into some
> number of disk blocks (no wasted space!).
I actually considered that. I ended up not doing it, because it's not
obvious how to "block" things up (and even more so because while I like
the notion, it flies in the face of the other issues I had: performance
and simplicity).
The problem with chunking is:
- it complicates a lot of the routines. Things like "is this file
unchanged" suddenly become "is this file still the same set of chunks",
which is just a _lot_ more code and a lot more likely to have bugs.
- you have to find a blocking factor. I thought of just going it fixed
chunks, and that just doesn't help at all.
- we already have wasted space due to the low-level filesystem (as
opposed to "git") usually being block-based, which means that space
utilization for small objects tends to suck. So you really want to
prefer objects that are several kB (compressed), and a small block just
wastes tons of space.
- there _is_ a natural blocking factor already. That's what a file
boundary really is within the project, and finding any other is really
quite hard.
So I'm personally 100% sure that it's not worth it. But I'm not opposed to
the _concept_: it makes total sense in the "filesystem" view, and is 100%
equivalent to having an inode with pointers to blocks. I just don't think
the concept plays out well in reality.
Linus
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox